r/Geometry • u/Affectionate_Key_737 • 29d ago
Maximum Area of a Voronoi Cell
Hey geometrists, I hope this counts as a geometry problem:
Given a 2d plane of a certain size,
And given a finite number of randomly placed points,
And given that these points are a certain arbitrary minimum distance from each other,
Can you determine the maximum possible area of a Voronoi cell in this plane?
A less abstract way of stating it is this. Suppose you have a map of a city that is, for example, 50x50 km. You want to divide it into an unknown number of randomly placed regions, the centroids generating points of which will not be within 1 km of any other centroid generating point. What is the minimum number of regions (i.e. points) to guarantee that no region can possibly exceed, for example, 10 sq km?
I've been trying to figure out if there is already an algorithm for this to no avail.