Let's say I have a fixed number (X) of points, e.g. coordinates within a given plane (I think you can call it a 2-D point cloud).

These points should be partitioned into Y polygons where Y < X. The polygons should not overlap. It would be wonderful if the polygons were konvex (like a Voronoi diagram).

Imagine it like locations forming countries. For example, I have 12 points and want to create 3 polygons with 4 points each.

I thought about creating a grid which covers the points. Then iterate across the points, assigning them to the closest grid cells.

Maybe I miss the obvious? I am sure there are better solutions.

Thanks, Daniel

I just found an optimization (kmeans++) .Maybe this will yield better results..