First, I am embarrassed that I didn't spot the "bad mirror" that you found -- I routinely look for them. My nonexistence proof is similar to yours but clunkier: I focused on the presence of (2,0) rather than that of (0,1), and arrived at the same conclusion. Second, your algorithm is fabulous. Thank you very much. I now think that I can code up a disk-polyomino counter -- and I might even do it. On Fri, Jul 20, 2012 at 5:07 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
01 02 03 04 11 12 13 14 20 21 22 23 24 25 31 32 33 34 35 42 43 44.
No disc exists. The presence of (0,1) and absence of (4,1) implies that the centre lies to the left of x = 2, whereas the presence of (3,5) and absence of (1,5) implies that it lies to the right of x = 2.
More generally, this strategy can answer all questions of this form.
Call the points you specified 'interior', and everything else in Z^2 'exterior'. Draw every perpendicular bisector between {interior point, exterior point}, and exclude the region closer to the exterior point. At the end, we have either:
A) A convex polygon of possible centres; B) A proof of the non-existence of a valid disc.
In case B, we are done. Hence, we will assume that case A is true, and that there may exist a disc:
Choose an arbitrary point in the convex polygon, and call this O. Imagine a circle of centre O and initial radius 0, then start to continuously increase its radius. This will eventually contain all interior points and no exterior points, since otherwise it must be closer to an exterior point than an interior point.
For pretty boring reasons, we only need to consider the exterior points within a Chebyshev (king's-move) distance of 1 from the set of interior points. Hence, there is a finite set of points to consider, and we have an *algorithm* for determining whether a polyomino is a disc polyomino. Moreover, this runs in quadratic time in the number of interior points!
Sincerely,
Adam P. Goucher
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>