...

--Given a set of points P and another Q in the plane, the question of whether a disk D exists with P inside D but Q outside D, is a linear programming problem, for each point xy we demand a*x*x+b*x*y+a*y*y+c*x+d*y+e > 0 (or <0)

+ b*x*y ???

I don't think so; the general equation of a circle is:

A(x^2 + y^2) + Bx + Cy + D = 0

which forms a projective 3-space of possible circles.

--sorry, typo, I should have omitted the b*x*y term by making b=0. To correct+clarify: If you do a*x*x+b*x*y+c*y*y+d*x+e*y+f then by the linear programming approach you can decide separability of point set P from Q by any conic section (i.e. quadratic algebraic curve). Indeed in any fixed #dimensions D for any fixed-degree polynomial(x1,x2,...,xN) you can decide separability of two point sets via the algebraic surface defined by such a polynomial, via linear programming in the same kind of way. So anyway, back to the circle case, a*(x-x0)^2 + a*(y-y0)^2 - 1 = a*x*x+a*y*y-2*a*x0*x-2*a*y0*y + x0^2 + y0^2 - 1 (left hand side >0 or <0 if x,y outside/inside circle with center x0,y0 and radius^2=1/a) can be rewritten as a*x*x + a*y*y + b*x + c*y + d so the question of whether a separating circle exists is just a linear program in (a,b,c,d) to tell if (a,b,c,d) exist which cause the above expression to be >0 for points in one set and <0 for points in the other. And by solving this linear program you can find such a circle, indeed you can find the "best" such circle as I'd described. (You could also demand a>0 as an additional inequality in the linear program; this demand should be unnecessary but might lead to a speedup.)

It looks like you have a 4-parameter family of conic sections instead. But, yes, your idea does generalise to determining whether there exists an algebraic curve (within a particular pencil) which separates the sets P and Q.

--yes. But as I said above, it also works just for circles.

Returning to my original algorithm (just for discs), it is sufficient to check the interior points on the perimeter of the polyomino (for the same reason it is sufficient to check the exterior points adjacent to them). This reduces the running time from O(n^2) to O(n) for confirming a disc polyomino -- asymptotically, the best possible.

--the linear programming method will also run in optimal O(n) time. Specifically, it is known that solving a linear program with V variables and N inequalities can be done in O(N) time if V is fixed. I think this was first shown by Nimrod Megiddo 20-30 years ago but there are now many known algorithms to do it, the nicest being randomized algorithms, including ones by K.Clarkson and by R.Seidel.