Here's a question which annoyed me through the night.
Given a set of points, say:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
Call encoding any 2-dimensional array of size between between 2x2 and 50x50 (both dimensions can be different),
all of whose elements are either 0 or 1.
Call neighbour of a memberof an encoding any of the at most eight members of the array whose value is 1,m
and each of both indexes differs from's corresponding index by at most 1. Given a particular encoding, wem
inductively determine for all natural numbersthe set of polygons of depthd
(for this encoding) as follows:d
Let a
natural numberbe given, and suppose that for all d0 < d, the set of polygons of depth d0 has been determined.d
Change in the encoding all 1's that determine those polygons to 0. Then the set of polygons of depth d is determined
as the set of polygons which can be obtained from that encoding by connecting 1's with some of their neighbours
in such a way that we obtain a maximal polygon (that is, a polygon which is not included in any other polygon
obtained from that encoding by connecting 1's with some of their neighbours).
Create some integer B, set it to zero.
For every point p:
If p has not been marked as "been":
Mark p as "been"
BFS/DFS from p and count the number of adjacent reachable points. Also mark each of these points as "been".
If the number of reachable points + 1 is greater than B:
B = the number of reachable points + 1
At the end, B = the maximum size of the polygon (in points "covered").