[math-fun] Wechsler disk problem
From: Allan Wechsler <acwacw@gmail.com> Either find a circular disk that covers these lattice points and no others, or prove that no such disk exists.
Here is the set. I am abbreviating (x,y) to the two-digit code xy.
01 02 03 04 11 12 13 14 20 21 22 23 24 25 31 32 33 34 35 42 43 44.
--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) and the linear programming will determine whether suitable (a,b,c,d,e) exist. Indeed by replacing the >0 by ">s" and the <0 by "< -s" and maximizing s, you can make the linear program find the "best" such circular disk (if any exist). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
--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. 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. -------- 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. Sincerely, Adam P. Goucher
On Sat, Jul 21, 2012 at 6:46 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
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.
Your algorithm isn't quite O(n) yet; for some polyominoes, the number of boundary points is not O(sqrt(n)); the straight polyomino of length n has n interior and 2n+2 exterior boundary points to consider. And you can't just exclude these for not being disclike, because you can't reject the non-disclike polyominoes until you know which they are, and that's what you're trying to figure out! But the algorithm can be patched up to be O(n), though the details are messy. For small n, do whatever you like; it doesn't effect the asymptotic behavior. For large n, first count the boundary points, interior and exterior, that you would use to apply your algorithm. If there are more than, say, 10 sqrt(n) such points, reject the polyomino as non-disclike. Otherwise, apply your algorithm. This is an existence proof of an O(n) algorithm without an explicit algorithm, since I don't know how large a value of n should be considered "large", and choosing too small a cutoff will give incorrect results. Andy
participants (3)
-
Adam P. Goucher -
Andy Latto -
Warren Smith