I would like to generate some random set of points so that their Voronoi diagram consist of equal-area polygons. Is it possible to impose some constraints on the points in order to have the same areas (or at least almost the same) of polygons? Regular polygons are not interesting.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Let us assume that we are building a diagram inside a certain circle (or certain finite polygon) $\endgroup$– Андрей ВоронцовCommented Dec 14, 2016 at 22:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I think that this paper addresses your question, if you stipulate a constant density distribution:
Balzer, Michael, Thomas Schlömer, and Oliver Deussen. Capacity-constrained point distributions: A variant of Lloyd's method. Vol. 28. No. 3. ACM SIGGRAPH, 2009. (ACM link).
"[...] This constraint enforces that each point in a distribution has the same capacity. Intuitively, the capacity can be understood as the area of the point’s corresponding Voronoi region weighted with the given density function. By demanding that each point’s capacity is the same, we ensure that each point obtains equal importance in the resulting distribution."
I believe this can be viewed as a form of an optimal transport problem.
answered Dec 15, 2016 at 1:36
-
1$\begingroup$ As I read it, that 2009 paper proposes an algorithm to do this, but only evaluates the algorithm's correctness empirically, without proof. They do cite a 1998 paper by Aurenhammer et al [Algorithmica (1998) 20: 61–76] that proves that there is a "power diagram" with equal-capacity regions, but a power diagram is not (in general) a Voronoi diagram. Am I missing something? $\endgroup$ Commented Jul 31, 2017 at 21:40