[math-fun] Disk polyomino puzzle
It's difficult to enumerate disk polyominoes, because it's hard to recognize them. To illustrate this, I present a modest puzzle. I will give a set of lattice points. 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.
It's difficult to enumerate disk polyominoes, because it's hard to recognize them. To illustrate this, I present a modest puzzle. I will give a set of lattice points. 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.
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. Sincerely, Adam P. Goucher
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
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>
participants (2)
-
Adam P. Goucher -
Allan Wechsler