Find Voronoi tessellation with area constraints

Question

Let's say we want to Voronoi-partition a rectangular surface with N points. The Voronoi tessellation results in N regions corresponding to the N points. For each region, we calculate its area and divide it by the total area of the whole surface - call these numbers a1, ..., aN. Their sum equals unity.

Suppose now we have a preset list of N numbers, b1, ..., bN, their sum equaling unity.

How can one find a choice (any) of the coordinates of the N points for Voronoi partitioning, such that a1==b1, a2==b2, ..., aN==bN?

Edit:

After a bit of thinking about this, maybe Voronoi partitioning isn't the best solution, the whole point being to come up with a random irregular division of the surface, such that the N regions have appropriate sizes. Voronoi seemed to me like the logical choice, but I may be mistaken.

Answer 1

I'd go for some genetic algorithm.

Here is the basic process:

1) Create 100 sets of random points that belong in your rectangle.

2) For each set, compute the voronoï diagram and the areas

3) For each set, evaluate how well it compares with your preset weights (call it its score)

4) Sort sets of points by score

5) Dump the 50 worst sets

6) Create 50 new sets out of the 50 remaining sets by mixins points and adding some random ones.

7) Jump to step 2 until you meet a condition (score above a threshold, number of occurrence, time spent, etc...)

You will end up (hopefully) with a "somewhat appropriate" result.

Answer 2

If what you are looking for does not necessarily have to be a Voronoi tesselation, and could be a Power diagram, there is a nice algorithm described in the following article:

F. Aurenhammer, F. Hoffmann, and B. Aronov, "Minkowski-type theorems and least-squares clustering," Algorithmica, 20:61-76 (1998).

Their version of the problem is as follows: given N points (p_i) in a polygon P, and a set of non-negative real numbers (a_i) summing to the area of P, find weights (w_i), such that the area of the intersection of the Power cell Pow_w(p_i) with P is exactly a_i. In Section 5 of the paper, they prove that this problem can be written as a convex optimization problem. To implement this approach, you need:

• software to compute Power diagrams efficiently, such as CGAL and
• software for convex optimization. I found that using quasi-Newton solvers such as L-BFGS gives very good result in practice.

I have some code on my webpage that does exactly this, under the name "quadratic optimal transport". However this code is not very clean nor very well-documented, so it might be as fast to implement your own version of the algorithm. You can also look at my SGP2011 paper on this topic, which is available on the same page, for a short description of the implementation of Aurenhammer, Hoffman and Aronov's algorithm.

Answer 3

Assume coordinates where the rectangle is axis-aligned with left edge at x = 0 and right edge at x = 1 and horizontal bisector at y = 0. Let B(0) = 0 and B(i) = b1 + ... + bi. Put points at ((B(i-1) + B(i))/2, 0). That isn't right. We the x coordinates to be xi such that bi = (x(i+1) - x(i-1)) / 2, replacing x(0) by 0 and x(n+1) by 1. This is tridiagonal and should have an easy solution, but perhaps you don't want such a boring Voronoi diagram though; it will be a bunch of vertical divisions.

For a more random-looking diagram, maybe something physics inspired: drop points randomly, compute the Voronoi diagram, compute the area of each cell, make overweight cells attractive to the points of their neighbors and underweight cells repulsive and compute a small delta for each point, repeat until equilibrium is reached.

Answer 4

The voronoi tesselation can be compute when you compute the minimum spanning tree and remove the longest edges. Each center of the subtree of the mst is then a point of the voronoi diagram. Thus the voronoi diagram is a subset of the minimum spanning tree.