Dense Point Sets Have Sparse Delaunay Triangulations

Title: Dense Point Sets Have Sparse Delaunay Triangulations

Research Question: How does the spread of a point set in R3 affect the complexity of its Delaunay triangulation?

Methodology: The study uses the spread of a point set, which is the ratio between the longest and shortest pairwise distances, to analyze the complexity of the Delaunay triangulation. The spread is a measure of how well-spaced the points are, and it is particularly relevant for dense point sets.

Results: The main result is that the Delaunay triangulation of any set of points in R3 with spread ∆ has complexity O(∆3). This bound is independent of the number of points in the set. In other words, the triangulation has linear complexity for dense point sets. The bound is tight in the worst case for all ∆ = O(√n), and it improves upon the previous upper bound of O(∆4).

Implications: These results have significant implications for computational geometry and applications that rely on Delaunay triangulations, such as nearest-neighbor searching, clustering, and mesh generation. The findings suggest that the complexity of Delaunay triangulations for dense point sets is much lower than previously thought, which could lead to more efficient algorithms and better performance in practical scenarios.

Link to Article: https://arxiv.org/abs/0110030v2 Authors: arXiv ID: 0110030v2