A comparison of sequential Delaunay triangulation algorithms.

DOI10.1016/S0925-7721(96)00025-9zbMATH Open1133.68466OpenAlexW2208229792MaRDI QIDQ2482895FDOQ2482895

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

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

zbMATH Keywords

Delaunay triangulationVoronoi diagramExperimental analysis of algorithmsPractical algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• An empirical comparison of techniques for updating Delaunay triangulations
• Parallel Delaunay triangulation in three dimensions
• Thread-parallel mesh improvement using face and edge swapping and vertex insertion
• HCPO: an efficient insertion order for incremental Delaunay triangulation
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Three-dimensional unstructured gridding for complex wells and geological features in subsurface reservoirs, with CVD-MPFA discretization performance
• A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case
• Regular triangulations of dynamic sets of points
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• Solutions to the Minimum Variance Problem Using Delaunay Triangulation
• RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point
• Fast reconstruction of Delaunay triangulations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing Delaunay Triangulations along Space-Filling Curves
• DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\).
• Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance
• THE DELAUNAY HIERARCHY

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)