8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Let us assume that we are building a diagram inside a certain circle (or certain finite polygon) $\endgroup$ Dec 14, 2016 at 22:04

1 Answer 1

5
$\begingroup$

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).


Fig3


"[...] 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.

$\endgroup$
1
  • 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$
    – Neal Young
    Jul 31, 2017 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.