# How to create polygons over a specific number of points

I came upon this question in a non GIS-related task, but it really interests me how to do a similar thing in GIS-systems.

Problem:

• Imagine a random point pattern (see image below)
• Now what i want to have is the maximal number of polygons over the whole area, which:
• enclose a specific number of points (x), which for example could be 4 points
• don't overlap. No polygon should not touch each other!

Possible extension: All polygons have to have equal size
Edit:The shape of the polygons is not important for now. Even Minimum-Convex-Polygons (MCP) are possible.

So some kind of triangulation, which takes the number of points and the position of the resulting polygon into consideration.

Anyone knows of an algorithm to solve this problem?

-
If the polygons can be concave, the answer is point count / 4. –  Russell at ISC Jun 24 at 19:06
To augment the comment by @Russell at ISC, a quick line-scan algorithm will pick up points one by one; as each group of four points is obtained, they form a polygon. These polygons obviously cannot overlap. (The algorithm has to be modified slightly to cope with special cases where multiple points are scanned simultaneously.) Another solution is to create a non-self-intersecting polyline from the points, buffer it a tiny amount, and split it into pieces that cover four points each. All this shows that the problem is underdetermined. –  whuber Jun 24 at 19:15
@Russel: Yeah, this gives you a possible number of resulting polygons, but i want the exact locations and they should not overlap. whuber: What you do you mean with scan-line algoritm (wikip. didn't help me and point by point sounds to simple for me). Remember that the solution would be the maximal possible number of covering polygons. Point patterns can be totally random, even clustered and x can have varying (unequal) sizes, which might result in non optimal solutions (for instance 10 resulting polygons, where 11 might have been possible). –  Curlew Jun 24 at 19:52
As @Russell points out, specifying a maximum number doesn't do anything for you: it is achieved by any algorithm that uses four points per polygon. In fact, corresponding to any partition of a set of N points into subsets of four or more elements, there will be infinitely many solutions: just create a linear (abstract) graph of each subset and find a planar embedding of the resulting (disconnected) graph, then buffer it a tiny bit. This is always possible, regardless of how the points are situated. –  whuber Jun 24 at 20:20
The "line-scan algorithm" is often called a line sweep algorithm. –  whuber Jun 24 at 21:02