A comparison of sequential Delaunay triangulation algorithms.

DOI10.1016/S0925-7721(96)00025-9MaRDI QIDQ2482895zbMATH OpenOpenAlexFDO

Authors Peter Su, R. L. 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

Delaunay triangulationVoronoi diagramExperimental analysis of algorithmsPractical algorithms

Mathematics Subject Classification ID

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

Recommendations

• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• scientific article; zbMATH DE number 4062599
• A fast algorithm for constructing Delaunay triangulations in the plane
• A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case
• Fast Delaunay triangulation in three dimensions

Cites work

• scientific article; zbMATH DE number 4062599 (Why is no real title available?)
• scientific article; zbMATH DE number 176491 (Why is no real title available?)
• scientific article; zbMATH DE number 3533716 (Why is no real title available?)
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• A new algorithm for three-dimensional Voronoi tessellation
• A sweepline algorithm for Voronoi diagrams
• Algorithms for parallel memory, I: Two-level memories
• Applications of random sampling in computational geometry. II
• Computing Dirichlet Tessellations in the Plane
• Convex hulls of finite sets of points in two and three dimensions
• Delaunay triangulation and the convex hull of n points in expected linear time
• Higher-dimensional Voronoi diagrams in linear expected time
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• On the randomized construction of the Delaunay tree
• Optimal Expected-Time Algorithms for Closest Point Problems
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Voronoi diagrams and arrangements
• Voronoi diagrams from convex hulls

Cited in

(19)

• DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\).
• A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case
• Constructing Delaunay Triangulations along Space-Filling Curves
• Solutions to the Minimum Variance Problem Using Delaunay Triangulation
• An evaluation of point-insertion sequences for incremental Delaunay tessellations
• Regular triangulations of dynamic sets of points
• Fast reconstruction of Delaunay triangulations
• 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
• THE DELAUNAY HIERARCHY
• Thread-parallel mesh improvement using face and edge swapping and vertex insertion
• Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance
• HCPO: an efficient insertion order for incremental Delaunay triangulation
• An empirical comparison of techniques for updating Delaunay triangulations
• Parallel Delaunay triangulation in three dimensions
• scientific article; zbMATH DE number 4062599 (Why is no real title available?)
• scientific article; zbMATH DE number 5019916 (Why is no real title available?)
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• Fully dynamic Delaunay triangulation in logarithmic expected per operation

Describes a project that uses

Uses Software

• Voronoi

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

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