TL;DR
This paper introduces a novel probabilistic algorithm for computing Delaunay triangulations in high dimensions. By leveraging a "witness complex" and a geometric application of the Lovász local lemma, the algorithm avoids computationally expensive high-degree predicates, relying solely on squared distance comparisons. This leads to a sublinear time complexity in the number of witnesses and guarantees a certain level of simplex quality.
What Problem Does This Paper Address?
Computing Delaunay triangulations, a fundamental structure in computational geometry with applications in mesh generation, interpolation, and more, becomes computationally challenging in higher dimensions ($d$). The core difficulty lies in the "in-sphere predicate," which determines if a point lies inside, on, or outside the sphere circumscribing a set of $d+1$ points. This predicate involves evaluating a polynomial of degree $d+2$. As $d$ increases, this polynomial becomes increasingly complex and difficult to evaluate robustly and efficiently, especially with finite-precision arithmetic. Existing methods struggle with this algebraic complexity. This paper aims to overcome this by developing an algorithm that bypasses the need for high-degree predicates, instead relying on simpler, degree-2 operations (squared distance comparisons).
Methods
The paper's core contribution is a probabilistic algorithm that constructs a Delaunay triangulation by first building a "witness complex." The witness complex is a weaker form of the Delaunay complex, defined using a set of "witness" points. The key idea is that under certain conditions, the witness complex can coincide with the Delaunay triangulation.
The algorithm proceeds in two main phases:
- Witness Complex Construction: The algorithm computes the witness complex $\mathrm{Wit}(L, W)$ using only squared distance comparisons. This is a significant simplification compared to traditional methods.
- Perturbation and Identity Guarantee: When the set of witnesses $W$ is finite, $\mathrm{Wit}(L, W)$ might not be equal to the Delaunay triangulation $\mathrm{Del}(L)$. To bridge this gap, the algorithm introduces a novel perturbation scheme. It slightly modifies the input point set $L$ to $L'$ such that $\mathrm{Wit}(L', W) = \mathrm{Del}(L')$. This perturbation is inspired by the Moser-Tardos constructive proof of the Lovász local lemma. The algorithm iteratively perturbs points that cause the witness complex to deviate from being a Delaunay triangulation, ensuring that the final output is indeed a Delaunay triangulation.
Crucially, the algorithm avoids computing explicit coordinates or high-degree predicates. Instead, it relies on distance comparisons and a combinatorial criterion (good links) to ensure the output is a valid Delaunay triangulation.
Datasets
Not discussed in the paper. The algorithm operates on abstract point sets and their inter-point distances, rather than specific datasets.
Key Insights and Ideas
- Witness Complex as a Proxy: The witness complex provides a computationally tractable approximation of the Delaunay complex, especially when using only distance comparisons.
- Lovász Local Lemma for Geometric Perturbation: The paper ingeniously applies the probabilistic machinery of the Lovász local lemma to guide a geometric perturbation process. This allows for controlled adjustments to the point set to achieve the desired Delaunay triangulation.
- Sublinear Complexity in Witnesses: The algorithm achieves a time complexity that is sublinear in the number of witnesses ($|W|$). This is a major advantage when dealing with large sets of witness points.
- Avoiding High-Degree Predicates: The reliance solely on squared distance comparisons (degree 2) is a critical breakthrough for robustness and efficiency in higher dimensions, circumventing the notorious difficulty of exact high-degree polynomial evaluations.
- Guaranteed Simplex Thickness: Despite not explicitly optimizing for simplex quality, the algorithm guarantees a lower bound on the thickness of the output simplices, which is related to their "well-shapedness."
Key Results
- The algorithm computes a Delaunay triangulation using only squared distance comparisons.
- The time complexity is sublinear in the number of witnesses ($|W|$), specifically $O(|L| \cdot (\frac{|L|}{\mu})^{d^2+d} \log \frac{\lambda}{\epsilon})$, where $\lambda$ and $\mu$ are parameters of the input point set, and $\epsilon$ is related to the desired precision. The constants depend only on the dimension $d$.
- The algorithm guarantees that the output Delaunay simplices are $\delta^*$-protected, which implies a lower bound on their thickness.
- The number of point perturbations performed by the algorithm is expected to be linear in the number of input points $|L|$.
Limitations and Future Work
- Dependence on Parameters: The algorithm's performance and guarantees depend on parameters like $\lambda$ (sampling radius) and $\mu$ (sparsity ratio) of the input point set. The analysis assumes certain relationships between these parameters and the dimension $d$.
- Boundary Handling: The current algorithm is designed for the torus ($T^d$) and does not directly handle triangulations with boundaries in $\mathbb{R}^d$. The paper discusses an alternative approach for $\mathbb{R}^d$ that involves adding "phantom points" but notes it complicates the analysis.
- Future Work: The authors suggest that the techniques can be extended to construct weighted Delaunay triangulations and Delaunay triangulations on manifolds. They also mention that the analysis of the perturbation process yields improved bounds on protection and thickness compared to previous work.
Summary updated