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

DOI10.1145/2462356.2462404MaRDI QIDQ5174489zbMATH OpenOpenAlexFDO

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

Publication date 17 February 2015

Published in Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0524

zbMATH Keywords

Delaunay refinementmesh generationoutput sensitive algorithmsVoronoi diagramsVoronoi refinement

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an approximate Delaunay graph on the output points. Our algorithm runs in expected time $O(2^{O(d)}(nlogn+m))$, where $n$ is the input size, $m$ is the output point set size, and $d$ is the ambient dimension. The constants only depend on the desired element quality bounds. To gain this new efficiency, the algorithm approximately maintains the Voronoi diagram of the current set of points by storing a superset of the Delaunay neighbors of each point. By retaining quality of the Voronoi diagram and avoiding the storage of the full Voronoi diagram, a simple exponential dependence on $d$ is obtained in the running time. Thus, if one only wants the approximate neighbors structure of a refined Delaunay mesh conforming to a set of input points, the algorithm will return a size $2^{O(d)}m$ graph in $2^{O(d)}(nlogn+m)$ expected time. If $m$ is superlinear in $n$, then we can produce a hierarchically well-spaced superset of size $2^{O(d)}n$ in $2^{O(d)}nlogn$ expected time.

Recommendations

• Dynamic well-spaced point sets
• Dynamic well-spaced point sets
• Beating the spread, time-optimal point meshing

Cited in

(8)

• Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
• Dynamic well-spaced point sets
• Randomized incremental construction of Delaunay triangulations of nice point sets
• scientific article; zbMATH DE number 6693709 (Why is no real title available?)
• Approximating nearest neighbor distances
• Algorithm 1012
• Beating the spread, time-optimal point meshing
• Dynamic well-spaced point sets

Describes a project that uses

Uses Software

• TetGen

This page was built for publication: A fast algorithm for well-spaced points and approximate Delaunay graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5174489)