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