A faster divide-and-conquer algorithm for constructing Delaunay triangulations

DOI10.1007/BF01840356zbMath0631.68043OpenAlexW1991064236MaRDI QIDQ1094872

Rex A. Dwyer

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01840356

zbMATH Keywords

analysis of algorithmsVoronoi diagramcomputational geometryDelaunay triangulationaverage-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Geometric probability and stochastic geometry (60D05) Polyhedra and polytopes; regular figures, division of spaces (51M20) Algorithms in computer science (68W99)

Related Items

HCPO: an efficient insertion order for incremental Delaunay triangulation, A faster circle-sweep Delaunay triangulation algorithm, A divide-and-conquer algorithm for constructing relative neighborhood graph, Reprint of: Delaunay refinement algorithms for triangular mesh generation, A comparison of sequential Delaunay triangulation algorithms., SAR imaging simulation for an inhomogeneous undulated lunar surface based on triangulated irregular network, The maximum opposite angulation for mesh construction, Delaunay-based derivative-free optimization via global surrogates. I: Linear constraints, Delaunay-based derivative-free optimization via global surrogates. II: Convex constraints, Minimal roughness property of the Delaunay triangulation, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Higher-dimensional Voronoi diagrams in linear expected time, Triangulations in CGAL, Delaunay refinement algorithms for triangular mesh generation, LOOK: A lazy object-oriented kernel design for geometric computation

Cites Work

• Unnamed Item
• Unnamed Item
• Delaunay triangulation and the convex hull of n points in expected linear time
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two algorithms for constructing a Delaunay triangulation
• Optimal Expected-Time Algorithms for Closest Point Problems
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Two Dimensional Interpolation from Random Data
• Computing Dirichlet Tessellations in the Plane
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees