Orphan-Free Anisotropic Voronoi Diagrams

Guillermo D. Cañas, Steven J. Gortler

TL;DR

Anisotropic Voronoi Diagrams (AVDs) are powerful tools for spatial partitioning where "distance" changes depending on direction and location, but they often suffer from "orphans"—disconnected fragments of a cell. This paper proves that if your sample points form a sufficiently dense and well-spaced $\epsilon$-net, these orphans are guaranteed to vanish, resulting in well-behaved, star-shaped Voronoi regions in any number of dimensions.

What Problem Does This Paper Address?

In a standard Voronoi diagram, space is partitioned into regions based on the closest "site." In Euclidean space, these regions are always convex and connected. However, many real-world problems—like mesh generation for fluid dynamics or image compression—require anisotropy, where the metric (the ruler used to measure distance) varies across the domain.

When you move from Euclidean distance to a Riemannian metric, the "niceness" of Voronoi diagrams breaks. A single site’s region can split into multiple disconnected pieces, known as orphans. These orphans make the diagrams incredibly difficult to compute and break the mathematical properties needed to create high-quality triangular meshes (the dual Delaunay triangulation). While previous research provided some guarantees for 2D diagrams, a general proof for higher dimensions remained elusive.

Methods

The authors focus on two popular approximations of geodesic distance used in AVDs:

  1. Labelle/Shewchuk (LS) diagrams: The metric is evaluated only at the site.
  2. Du/Wang (DW) diagrams: The metric is evaluated at the point being measured.

The core of their approach is the use of an asymmetric $\epsilon$-net. An $\epsilon$-net is a set of points that satisfies two conditions:

  • Covering: No point in the space is further than $\epsilon$ from a site.
  • Packing: No two sites are too close to each other.

By defining a "maximum variation" constant ($\sigma$) that describes how quickly the underlying metric changes, the authors use a contradiction-based proof. They show that if an orphan were to exist, the distance function along a line segment between a site and its orphan would have to behave in a way that violates the $\epsilon$-net properties.

Datasets

As this is a theoretical paper in computational geometry, no empirical datasets or benchmarks were used. The "data" consists of the mathematical definitions of Riemannian metrics and the geometric properties of Voronoi cells.

Key Insights and Ideas

  • Density Alone is Insufficient: A common intuition is that simply adding more points (increasing density) will eventually eliminate orphans. The authors show this is false; you specifically need the packing property (sites must be spaced out relative to the metric) to guarantee orphan-freeness.
  • Star-Shapedness: The authors prove something stronger than mere connectivity. They show that Voronoi regions under these conditions are star-shaped with respect to their sites. This means every point in a region has a direct, straight-line path to its site that stays entirely within the region.
  • Dimension Independence: Perhaps the most surprising finding is that the bounds for orphan-freeness do not depend on the number of dimensions ($n$). Whether you are working in 2D or 10D, the same relationship between $\epsilon$ and $\sigma$ holds.
  • Practical Greedy Algorithms: The paper notes that existing greedy site-insertion algorithms (which pick the point furthest from all current sites to place the next one) naturally produce the $\epsilon$-nets required by their theorems.

Key Results

The paper establishes specific theoretical thresholds for the product of the net density ($\epsilon$) and the metric variation ($\sigma$):

  • Du/Wang Diagrams: Guaranteed to be orphan-free if $\epsilon\sigma \leq 0.09868$.
  • Labelle/Shewchuk Diagrams: Guaranteed to be orphan-free if $\epsilon\sigma \leq 0.0584$.

These constants provide a "guaranteed safety zone" for researchers building mesh generation software or optimization algorithms, ensuring that their spatial partitions won't fragment into a mess of disconnected pieces.

Limitations and Future Work

The authors acknowledge that their derived bounds ($\epsilon\sigma \leq 0.0584$) are likely conservative. In practice, diagrams might become orphan-free at much lower densities than the proof requires.

The most significant direction for future work is connecting "orphan-freeness" to the quality of the dual simplicial complex (the anisotropic Delaunay triangulation). While they have proved the Voronoi cells are well-behaved, they haven't yet proven that the resulting triangular mesh is free of "inverted" or "flipped" elements in higher dimensions, though they suspect orphan-freeness is a critical step toward that goal.

Summary updated

Abstract

We describe conditions under which an appropriately defined anisotropic Voronoi diagram of a set of sites in Euclidean space is guaranteed to be composed of connected cells in any number of dimensions. These conditions are natural for problems in optimization and approximation, and algorithms already exist to produce sets of sites that satisfy them.
BibTeX
@inproceedings{canas2011orphan,
  author = {Guillermo D. Cañas and Steven J. Gortler},
  title = {{Orphan-Free Anisotropic Voronoi Diagrams}},
  booktitle = {Discret. Comput. Geom},
  year = {2011},
  url = {https://openreview.net/forum?id=lNLTnICoSA_},
}

Loading related content...

Figure