I have a complex polygon like this one. Polygon of Croatia
It is filled with about $16$k points with non-uniform density. I want to segment the polygon into parts that have the same number of points. I understand this is a very complex problem but I don't need it to be mathematically perfect. I would be fine with ~$10\%$ error from wanted number of points in each segment. To make my life easier I could first split the polygon into minimum number of convex parts.
The ideas I have so far:
Pack the polygon with circles of varying radii based on the number of points within the circle and then use the centers of those circles to create a Voronoi diagram to fill in the gaps. I'm still not sure how I would achieve the packing part.
Make repeated offsets of each convex part inwards and split the strip I get into segments based on the number of points inside it. Here's a simplified diagram of what I mean: Example
Triangles?
Edit: A requirement I forgot to mention is that the groups of points would have to be close and not scattered across the polygon. I want each point in a segment to be relevant to that segment because I will be using a model to classify future points.
I'd also like for the algorithm to be deterministic ie. I want to get the same output each time I run it on the same points in the same order. If I assume the points are distributed uniformly, how much easier does that make the problem? I've been thinking about this for a while and I'd like to get some pointers and ideas from people that understand this kind of geometry better than me. Thanks!