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.
Introduction: The Challenge of Anisotropy
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 applications—such as mesh generation for fluid dynamics or image compression—require anisotropy, where the metric (the ruler used to measure distance) varies across the domain depending on direction and location.
When transitioning from Euclidean distance to a Riemannian metric, the geometric stability of Voronoi diagrams often collapses. A single site’s region can split into multiple disconnected pieces, known as orphans. These orphans make diagrams computationally difficult to manage and break the mathematical properties required to generate high-quality triangular meshes. While previous research provided guarantees for 2D diagrams, a general proof for higher dimensions has remained elusive until now.
Methods: The Power of $\epsilon$-Nets
The authors investigate two primary approximations of geodesic distance used in Anisotropic Voronoi Diagrams (AVDs):
- Labelle/Shewchuk (LS) diagrams: The metric is evaluated only at the site.
- Du/Wang (DW) diagrams: The metric is evaluated at the point being measured.
The core of their theoretical framework relies on the use of an asymmetric $\epsilon$-net. An $\epsilon$-net is a set of points that satisfies two critical conditions:
- Covering: No point in the space is further than $\epsilon$ from a site.
- Packing: No two sites are too close to each other (relative to the metric).
By defining a "maximum variation" constant ($\sigma$) that describes the rate of change of the underlying metric, the authors employ a contradiction-based proof. They demonstrate that if an orphan were to exist, the distance function along a line segment between a site and its orphan would necessarily violate the fundamental properties of the $\epsilon$-net.
Key Insights
- Packing is Essential: A common misconception is that simply increasing point density will eliminate orphans. The authors prove that density alone is insufficient; the packing property (ensuring sites are adequately spaced) is the key to guaranteeing orphan-freeness.
- Star-Shapedness: The proof establishes a property stronger than simple connectivity: Voronoi regions under these conditions are star-shaped with respect to their sites. This ensures every point in a region has a direct, straight-line path to its site that remains entirely within the region.
- Dimension Independence: Remarkably, the bounds for orphan-freeness do not depend on the number of dimensions ($n$). The same relationship between $\epsilon$ and $\sigma$ holds whether the space is 2D or 10D.
- Algorithmic Compatibility: Existing greedy site-insertion algorithms, which iteratively place new sites at the point furthest from all current sites, naturally produce the $\epsilon$-nets required by these theorems.
Key Results and Thresholds
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, ensuring that spatial partitions will not fragment into disconnected pieces.
Limitations and Future Work
The authors acknowledge that their derived bounds are likely conservative; in practice, diagrams may become orphan-free at lower densities than the proof strictly requires. The most significant avenue for future research is connecting orphan-freeness to the quality of the dual simplicial complex (the anisotropic Delaunay triangulation). While the Voronoi cells are now proven to be well-behaved, proving that the resulting triangular mesh is free of "inverted" elements in higher dimensions remains the next major challenge.
Summary updated