A comparison of sequential Delaunay triangulation algorithms.

DOI10.1016/S0925-7721(96)00025-9zbMath1133.68466OpenAlexW2208229792MaRDI QIDQ2482895

Peter Su, Robert L. Scot Drysdale

Publication date: 25 April 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(96)00025-9

zbMATH Keywords

Voronoi diagramDelaunay triangulationExperimental analysis of algorithmsPractical algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (9)

Thread-parallel mesh improvement using face and edge swapping and vertex insertion ⋮ HCPO: an efficient insertion order for incremental Delaunay triangulation ⋮ Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance ⋮ Solutions to the Minimum Variance Problem Using Delaunay Triangulation ⋮ THE DELAUNAY HIERARCHY ⋮ Parallel Delaunay triangulation in three dimensions ⋮ Three-dimensional unstructured gridding for complex wells and geological features in subsurface reservoirs, with CVD-MPFA discretization performance ⋮ RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point ⋮ A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new algorithm for three-dimensional Voronoi tessellation
• Delaunay triangulation and the convex hull of n points in expected linear time
• Higher-dimensional Voronoi diagrams in linear expected time
• Voronoi diagrams and arrangements
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• A sweepline algorithm for Voronoi diagrams
• Voronoi diagrams from convex hulls
• Randomized incremental construction of Delaunay and Voronoi diagrams
• On the randomized construction of the Delaunay tree
• Algorithms for parallel memory, I: Two-level memories
• Applications of random sampling in computational geometry. II
• 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
• Optimal Expected-Time Algorithms for Closest Point Problems
• Convex hulls of finite sets of points in two and three dimensions
• Computing Dirichlet Tessellations in the Plane

This page was built for publication: A comparison of sequential Delaunay triangulation algorithms.