Finding Voronoi centers from a convex partition

From TheTangentSpace

A Voronoi diagram (named after Russian mathematician Georgy Voronoi) is a partition of a metric space based on a given subset of that space. Very often, as is the case for this page, the metric space used is Euclidean distance in . It is well-known how to derive a Voronoi partition from a set of points. This page discusses some thoughts about the inverse operation -- how to recover a set of points given a convex partition.

To very briefly give some definitions: given , we can write V(x) for any to denote the set . Intuitively, V(x) is the set of points which are closer to than any other point in X (with boundary included).

Not all Voronoi diagrams are convex partitions

But many are, including the Voronoi diagram for any closed set X in the norm for in . On this page we focus on a convex partition - a disjoint set of open convex sets whose complement (the boundaries of these sets) has zero measure. For more on when such a partition arises (or doesn't) in a Voronoi diagram, see Classifying Voronoi diagrams.

Not all convex partitions are Voronoi-able

Cases that are very hard to fix

Fig 1. Example convex partition which is not a simple Voronoi diagram

The image at the right (figure 1) gives a convex partition of the plane, represented by the solid colors, which cannot be realized as a simple Voronoi diagram. To see this, consider the 4 white dots which specify candidate Voronoi centers. In order for the 4 left shapes to be Voronoi cells, their Voronoi centers must form the corners of an axis-parallel rectangle concentric with the rays of of the partition.

A key observation here (and throughout these Voronoi pages) is that Voronoi centers in adjacent cells are the reflection of each other across their shared boundary. This justifies the rectangle classification of the white dots, and also gives us all possible candidate positions (exemplified by the pink dots in the red area) for the Voronoi centers in the red area. The dashed lines mark off all possible reflections from the yellow and purple areas -- and since these reflections have no overlap, there's no place that a Voronoi center could exist in the red area.

Edge cases (that we can sort of fix)

Fig 2. Example convex partition which is not normally expressible as a Voronoi diagram, but is if we allow either infinitesimals in the Voronoi centers, or, equivalently, a sequence of priorities on the centers.

Figure 2 shows a case in which we can almost create an equivalent Voronoi diagram. In this case, we can handle the partition in two ways:

• We can create a 2-step diagram, in which we first specify just two center points (the solid white dots) to separate the left and right areas, and next split the left point into two nearby points (the faded points) and consider this is a sub-Voronoi diagram of just the left area; or
• we can allow an infinitesimal unit in our coordinate system, and use the coordinates ( − 1,h),( − 1, − h), and (1,0) as the centers (where the origin is the center of figure 2).

I think these two methods will basically always be equivalent. The presence of an h in a coordinate can be ignored to find the first Voronoi diagram, and then we can split all h − level coordinates to get the 2nd step; next split all h² − level coordinates for the 3rd step, etc.

However, I don't believe either method can be applied to the partition of figure 1 since there is no clear way to separate the three right areas. Below there is a method described in which we can deal with these cases by creating a Voronoi diagram which contains any given partition as a sub-partition. Intuitively, if we are allowed to extend the horizontal separating line of figure 1 to the right side, then the 6 dots in the figure successfully give that partition as a Voronoi diagram.

How to find Voronoi centers in when we have at least two adjacent 3-intersections

This is a two-step process. First we find candidate points around a local circle of each intersection, and then find a mutual solution for the neighboring intersections. The nice thing about neighboring 3-intersections is that they provide unique Voronoi centers around any local circle, which means, if the partition is in fact a Voronoi diagram, we can uniquely determine all (finitely-connected) Voronoi centers. This follows because each Voronoi center is a reflection over every edge of the neighboring cell's Voronoi center.

Geometrically finding candidate centers of a 3-intersection

Fig 3. Randomly guess point 1, then reflect to find points 2,3,4. We choose point 5 as the average (on the circle) of points 1 and 4, and it follows that the reflections 6 and 7 form a closed reflection cycle, which indicates they work as Voronoi centers for this (part of the) partition.

Figure 3 illustrates a simple reflection algorithm which suffices to discover any existing Voronoi centers around an odd intersection. Begin by choosing any random point within a sector (one of the three angles of the intersection). Reflect that point in sequence around the boundary lines three times. All points so far lie on a single circle, and we may choose the unique point which is on the circle midway between our first random point and the last refected point - in the figure, we choose point 5 to be on the circle midway between points 1 and 4. If any Voronoi centers exist, this midway point is guaranteed to work as one of them, along with its reflections, which form a closed reflection cycle.

Why does this work? First observe that any valid Voronoi centers form a closed reflection cycle, since the boundary between any two Voronoi cells is the perpendicular bisector of the respective centers. Now consider the delta between points 1 and 5. After any number of reflections, that delta is preserved; after any odd number of reflections, the orientation is reversed. So after 3 reflections, we know that the unique point which gives the same delta in reversed orientations (that is, the midpoint) must be the Voronoi center (assuming it exists). Since the centers are all reflections of each other, it is trivial to find the other centers once we know a single one.

It also follows that, for even intersections, we may easily have infinitely-many valid Voronoi centers, since the delta's orientation is preserved. This means that, if there is at least one set of Voronoi centers with open neighborhoods within each sector, then any of those points will result in a closed reflection cycle and act as valid Voronoi centers.

So this algorithm really works for any (finite) intersection in (not just 3-intersections), as long as some Voronoi centers exist. Even if they do not exist, we find out quickly, since we can check if the resulting reflection cycle is a set of points all contained within their respective sectors.

Below we give algebraic variants which may appear completely superior to this method. So why bother with a geometric algorithm at all? In some cases, it's nice to have a geometric description of a construction, since it may help intuition for other investigations, and perhaps allow some generalization which fails for an algebraic version.

Algebraically finding candidate centers of an intersection

Suppose we are considering a k − intersection with rays (boundaries of the convex partition) at angles . Our goal is to find, if possible, angles so that

• s_i is between r_i and r_{i + 1}, and
• s_{i + 1} is the reflection of s_i over r_i (both with ).

This corresponds to finding Voronoi centers since we may choose any distance r > 0 and the points [r,s_i], as polar coordinates around the intersection, will work as the center points.

We can rigorize the desired conditions as

• s_i − r_i(mod 2π) < r_{i + 1} − r_i(mod 2π)

and

• s_{i + 1} = r_i + (r_i − s_i) = 2r_i − s_i(mod 2π).

Note that we can not write the first condition as r_i < s_i and s_i < r_{i + 1}(mod 2π), since each inequality alone is ambiguous modulo 2π. The way this condition - let's call it "betweenity" - is written is meant to indicate that the real number s_i − r_i(mod 2π) is smaller than the real number r_{i + 1} − r_i(mod 2π).

We can string the second condition together to arrive at When k is odd, we then get and similar equations for . In the case of k = 3, the equations which satisfy all conditions (possibly with non-strict betweenity) are:

Here is one way to see this conforms to the betweenity condition: The ray r_{i − 1} + π is (possibly non-strictly) between r_i and r_{i + 1} by convexity, which forbids any single angle beyond π. So r_{i + 1} − (r_{i − 1} + π) is a subangle of , and thus s_i is between the two; it is the other side of angle when pushed flush against r_i.

For larger odd k, once a value for s₁ is chosen (the choice is in the ( + π) term), all other s_i follow by reflection. If these s_i fail the betweenity condition, it must be that this partition is not Voronoiable. So we either immediately find viable Voronoi centers (possibly using infinitesimals), or know that it's impossible to do so.

For even k, we have no solutions when but, otherwise, any choice of s₁ will allow a sequence that satisfies the reflection condition.

Extending the circle-based candidates to unique centers

Each set of candidate Voronoi centers on a circle around an intersection can be considered as a set of rays, since the radius of the circle is variable. If we have two adjacent 3-intersections, then the rays in the common Voronoi cells intersect in a unique point (within that cell) which can work as a Voronoi center for both intersections simultaneously. From here, if the partition is Voronoiable, we can extend any known center to find all other centers (within finite cell distance) of the partition.

In summary, the above algorithm suffices to find Voronoi centers for any finitely-connected Voronoiable convex partition with adjacent 3-intersections.

Finding Voronoi centers of a refinement of any convex partition

Any two Voronoi centers whose perpendicular bisector matches a boundary of a convex partition will always separate the cells on either side of this boundary in their Voronoi diagram - no matter how many new points are introduced. So, for any convex partition, we can always choose a set of points which respects the divisions of the partition, although it may make more distinctions. In other words, even when a convex partition is not Voronoiable, we can find a refined partition - one with a superset of the boundaries - which is Voronoiable, along with its center points.

To do so, we simply need to find a set of centers such that every boundary is the perpendicular bisector of some pair of points. We can achieve this by finding candidate centers in a circle around every intersection -- we no longer need to worry about joining candidate centers by looking at the intersection of rays (although we could still try it if we prefer a smaller set of Voronoi centers).

As noted above, not every intersection allows a set of Voronoi centers which respect both the betweenity and the reflection conditions. It is fundamental that the betweenity condition be preserved, but we may relax the reflection condition to simply hold for some pair of points on opposite sides of a ray - not necessarily neighbors in a fixed sequence. Thus we can start by choosing any s₁ sufficiently close to r₂, and reflect to find s₂ so that s₂ satisifies betweenity. If the reflection of s₂ over r₃ fails betweenity, we can introduce a new point s₂' which is close enough to r₃ to fix this. Repeat this for every intersection to find a set of Voronoi centers whose Voronoi diagram is a refinement of the initial convex partition.

Future work

• Handle the general Voronoi-able convex partition -- that is, can we avoid assuming there are at least two adjacent 3-intersections?
• Is there a more elegant classification of which convex partitions are Voronoiable?
• Complete the generalization of this algorithm to higher dimensions.
• Can we extend this work to more general metric spaces?
• Are there any cool applications of this work?