A faster circle-sweep Delaunay triangulation algorithm

DOI10.1016/J.ADVENGSOFT.2011.09.003MaRDI QIDQ427141zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Gholamhossein Dastghaibyfard

Publication date 13 June 2012

Published in Advances in Engineering Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.advengsoft.2011.09.003

zbMATH Keywords

computational geometryDelaunay triangulationin-circle testrecursive edge-flippingsweep-circlesweep-line

Mathematics Subject Classification ID

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

Recommendations

• Algorithm for Delaunay triangulation and convex-hull computation using a sparse matrix
• A dynamic hierarchical subdivision algorithm for computing Delaunay triangulations and other closest-point problems
• DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\).
• A fast algorithm for constructing Delaunay triangulations in the plane
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4060717 (Why is no real title available?)
• scientific article; zbMATH DE number 3633698 (Why is no real title available?)
• scientific article; zbMATH DE number 1182913 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• A sweepline algorithm for Voronoi diagrams
• A weak characterisation of the Delaunay triangulation
• Constrained higher order Delaunay triangulations
• Delaunay triangulation and the convex hull of n points in expected linear time
• General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
• Generating realistic terrains with higher-order Delaunay triangulations
• Higher order Delaunay triangulations
• Higher-dimensional Voronoi diagrams in linear expected time
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Three-dimensional Delaunay mesh generation
• Two algorithms for constructing a Delaunay triangulation
• Voronoi diagrams from convex hulls

Cited in

(6)

• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
• A functional language to implement the divide-and-conquer Delaunay triangulation algorithm
• Algorithm for Delaunay triangulation and convex-hull computation using a sparse matrix
• A Robust Implementation for Three-Dimensional Delaunay Triangulations
• A triangulation algorithm based on edge-pointer search and region-division
• \textit{OFC}-Delaunay triangulation: a new efficient algorithm for merging two adjacent Delaunay triangulations

Describes a project that uses

Uses Software

• Voronoi
• Triangle

This page was built for publication: A faster circle-sweep Delaunay triangulation algorithm

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