Computing correct Delaunay triangulations

DOI10.1007/BF02242021MaRDI QIDQ1179540zbMATH OpenOpenAlexFDO

Authors D. Zepf, Michael Jünger, Gerhard Reinelt

Publication date 26 June 1992

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02242021

zbMATH Keywords

computational geometryDelaunay triangulationgeometric optimization algorithmsnumerically stable computer implementationVoronoj diagram

Mathematics Subject Classification ID

Triangulation and topological properties of semi-analytic andsubanalytic sets, and related questions (32B25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Technical questions about numerically stable computation of Delaunay triangulation and Voronoj diagram are investigated. The discussion is with respect to planar \(M\times M\) lattice where all generating points are supposed to be located. From \(M\) and underlying metrics \((L_ 1,L_ 2,L_ \infty)\) the necessary computer word length is derived. Correct and exact computations are possible for \(L_ \infty\) metric while for Euclidean \(L_ 2\) metric this technique is not successfully applicable.

Recommendations

• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• Delaunay triangulations in three dimensions with finite precision arithmetic
• Correct Delaunay triangulation in the presence of inexact inputs and arithmetic

Cites work

• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS

Cited in

(13)

• Computing bushy and thin triangulations
• Delaunay triangulations in three dimensions with finite precision arithmetic
• The finite volume method and application in combinations
• New primal and dual matching heuristics
• Correct Delaunay triangulation in the presence of inexact inputs and arithmetic
• Exact computation of Delaunay and power triangulations
• scientific article; zbMATH DE number 6379407 (Why is no real title available?)
• Delaunay properties of digital straight segments
• Star splaying
• A general approach to the analysis of controlled perturbation algorithms
• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• On sorting triangles in a Delaunay tessellation
• Triangulations from topologically correct digital Voronoi diagrams

This page was built for publication: Computing correct Delaunay triangulations

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