A fast algorithm for well-spaced points and approximate delaunay graphs

Gary L. Miller, Donald R. Sheehy, Ameya Velingker

Introduction

In computational geometry, Delaunay refinement is a cornerstone technique for generating high-quality meshes used in physics simulations, computer graphics, and data analysis. However, as the dimensionality of the space increases, traditional methods face a severe "curse of dimensionality." In their paper, Gary L. Miller, Donald R. Sheehy, and Ameya Velingker present a breakthrough: a fast, output-sensitive algorithm for generating well-spaced point sets and their corresponding approximate Delaunay graphs. This approach bypasses the combinatorial explosion typically associated with high-dimensional triangulations, offering a path forward for high-dimensional mesh generation.

The Challenge of High-Dimensional Meshing

Standard Delaunay refinement algorithms encounter two massive hurdles when moving beyond three dimensions:

  1. Combinatorial Blowup: In $d$ dimensions, a Delaunay triangulation of $n$ points can result in $O(n^{\lceil d/2 \rceil})$ simplices. Even in relatively low dimensions like $d=4$ or $d=5$, the number of elements becomes computationally unmanageable.
  2. Numerical Instability: Determining exact geometric relationships (predicates) for a valid triangulation is expensive and prone to floating-point errors.

Previous attempts at "near-optimal" algorithms often suffered from a dependence on the "spread" (the ratio of the largest to smallest distance in the input) or a superexponential dependence on the dimension. The authors sought a method that is truly output-sensitive and efficient as $d$ grows.

Methodology: Shifting from Simplices to Graphs

The authors depart from the traditional approach of maintaining a full simplicial complex. Instead, they maintain an Approximate Delaunay Graph (ADG). By focusing on the graph (the edges) rather than the full set of $d$-dimensional tetrahedra, the algorithm avoids the $O(n^{d/2})$ complexity.

Key Algorithmic Components

  • Greedy Permutation: The input points are pre-processed using farthest-point sampling. This ensures that each point inserted is relatively far from those already in the set, providing a structured foundation for the refinement process.
  • The Greedy Walk: For point location, the algorithm utilizes a "walk" through Voronoi cells. The authors prove that due to the greedy ordering of points, this walk takes only a constant number of steps on average to find a point's nearest neighbor, serving as an efficient alternative to complex data structures like KD-trees.
  • Approximate Linear Programming (LP): To refine the mesh, one must identify the "farthest corner" of a Voronoi cell to place a new Steiner point. Rather than constructing the complex Voronoi cell explicitly, the authors use the Ellipsoid Method to solve a Linear Program that finds an approximate farthest corner. This reframes a construction problem as an optimization problem, which scales significantly better with dimension.
  • Snapping: To maintain the "well-spaced" property without creating excessively small edges, the algorithm includes a snapping mechanism. If a new input point is too close to an existing Steiner point, the Steiner point is moved or replaced.

Theoretical Results

As a theoretical contribution, the paper establishes its results through rigorous mathematical proofs rather than empirical benchmarks. The key findings include:

  • Time Complexity: The algorithm runs in $O(2^{O(d)}(n \log n + m))$ expected time, where $n$ is the input size and $m$ is the output size. This near-linear dependence on $n$ and $m$ is a significant improvement over previous bounds.
  • Space Complexity: The output graph size is $2^{O(d)}m$. While still exponential in $d$, it is far superior to the $n^{d/2}$ complexity of exact Delaunay triangulations.
  • Quality Guarantees: The output is guaranteed to be $\tau$-well-spaced, meaning the Voronoi cells have a bounded aspect ratio, ensuring the geometric quality of the resulting point set.
  • Hierarchical Output: In scenarios where a linear-size mesh is impossible, the algorithm can produce a "hierarchically well-spaced" set of size $2^{O(d)}n$ in $O(2^{O(d)}n \log n)$ time.

Limitations and Future Outlook

While the algorithm represents a major theoretical leap, the authors acknowledge certain practical hurdles. The $2^{O(d)}$ constant factor, while an improvement, remains exponential and may become prohibitive for very high dimensions (e.g., $d > 20$). Furthermore, the algorithm produces an approximate Delaunay graph. While sufficient for many applications, certain Finite Element Methods (FEM) that require perfectly conforming simplicial meshes would require additional construction steps not explicitly covered here.

Ultimately, by demonstrating that one can maintain the benefits of Delaunay refinement through optimization and graph-based structures rather than explicit triangulation, this work provides a new framework for high-dimensional geometric computing.

Summary updated

BibTeX
@inproceedings{miller2013fast,
  author = {Gary L. Miller and Donald R. Sheehy and Ameya Velingker},
  title = {{A fast algorithm for well-spaced points and approximate delaunay graphs}},
  booktitle = {SoCG},
  year = {2013},
  doi = {10.1145/2462356.2462404},
}
Figure