A time-optimal delaunay refinement algorithm in two dimensions

DOI10.1145/1064092.1064128MaRDI QIDQ5370616zbMATH OpenOpenAlexFDO

Authors Alper Üngör, Sariel Har-Peled

Publication date 20 October 2017

Published in Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0501007

zbMATH Keywords

Delaunay triangulationmesh qualitymesh refinementquadtreeSteiner points

Mathematics Subject Classification ID

Steiner systems in finite geometry (51E10) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes $O(nlogn+m)$ time, where $n$ is the input size and $m$ is the output size. This is the first time-optimal Delaunay refinement algorithm.

Recommendations

• A time efficient Delaunay refinement algorithm
• An optimal algorithm for realizing a Delaunay triangulation
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation
• scientific article; zbMATH DE number 2066953
• A 2D advancing-front Delaunay mesh refinement algorithm
• Linear-time reconstruction of Delaunay triangulations with applications
• Delaunay triangulations of imprecise pointsin linear time after preprocessing

Cited in

(9)

• Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation
• Dynamic well-spaced point sets
• Diagonal swap procedures and characterizations of 2D-Delaunay triangulations
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• DELAUNAY REFINEMENT ALGORITHMS FOR ESTIMATING LOCAL FEATURE SIZE IN 2D AND 3D
• Beating the spread, time-optimal point meshing
• A time efficient Delaunay refinement algorithm
• Combining improvement and refinement techniques: 2D Delaunay mesh adaptation under domain changes
• Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations

This page was built for publication: A time-optimal delaunay refinement algorithm in two dimensions

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