A faster circle-sweep Delaunay triangulation algorithm

DOI10.1016/j.advengsoft.2011.09.003zbMath1239.68075OpenAlexW2081458114MaRDI QIDQ427141

Gholamhossein Dastghaibyfard, Ahmad Biniaz

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)

Related Items (1)

On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)

Uses Software

• Triangle
• Voronoi

Cites Work

• Delaunay triangulation and the convex hull of n points in expected linear time
• Higher-dimensional Voronoi diagrams in linear expected time
• Generating realistic terrains with higher-order Delaunay triangulations
• A weak characterisation of the Delaunay triangulation
• 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
• Higher order Delaunay triangulations
• Constrained higher order Delaunay triangulations
• General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
• Three-dimensional Delaunay mesh generation
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two algorithms for constructing a Delaunay triangulation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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