Partition 2D points into N regions each with K neighboring points

Question

If one has a collection of points in a 2D space, is there an algorithm that can break those points into N "regions" that each contain K neighboring points?

For example, suppose these 20 points are to be clustered into 4 groups each of 5 points. A satisfactory solution might look like this:

Motivation: I'm trying to optimize a visualization that loads lots of images into the browser. I'm planning to load very low-res images on page load then increase the resolution of images in a region as users zoom in on that region. Of course I'll need to quantize the space, so if users scroll straight into the middle of the sample above, I'd have to fetch high-res images for each of the 4 groups.

console.log('stackoverflow wants code for posts with codepen links')

Answer 1

An algorithm can be like this:

- get a triangulation of the points (for example: Delaunay Triangulation): D
- get a planar graph from D: G
- Then partition G into connected subgraphs with equal size k

For the last step this solution is short and easy (from Theoretical Computer Science site):

Compute a constant degree spanning tree T of your graph, root it, and now greedily find subtrees of roughly size r, extract them, and repeat. Naturally, if there is no constant degree spanning tree, then the star example shown above demonstrates that this algorithm can fail.