Delaunay triangulations in three dimensions with finite precision arithmetic

DOI10.1016/0167-8396(92)90044-PMaRDI QIDQ1195754zbMATH OpenOpenAlexFDO

Authors Chandrajit L. Bajaj, Tamal K. Dey, K. Sugihara

Publication date 18 January 1993

Published in Computer Aided Geometric Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8396(92)90044-p

zbMATH Keywords

algorithmDelaunay triangulationfinite precision arithmeticrobustness

Mathematics Subject Classification ID

Triangulation and topological properties of semi-analytic andsubanalytic sets, and related questions (32B25) Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The authors propose a modified version of a known algorithm for Delaunay triangulation of a given set in three-space to insure correct topology in finite precision arithmetic. They prove that their algorithm satisfies a well defined notion of robustness (assuming, as the authors do, that one does not run into trouble computing 5-by-5 determinants; it would be better to check whether a fifth point is or is not in the circumsphere of a tetrahedron without using determinants).

Recommendations

• Fast Delaunay triangulation in three dimensions
• Correct Delaunay triangulation in the presence of inexact inputs and arithmetic
• Exact computation of Delaunay and power triangulations
• Computing correct Delaunay triangulations
• Parallel Delaunay triangulation in three dimensions
• A Robust Implementation for Three-Dimensional Delaunay Triangulations
• Conforming Delaunay triangulations in 3D
• Conforming Delaunay triangulations in 3D

Cites work

• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 62659 (Why is no real title available?)
• scientific article; zbMATH DE number 3246034 (Why is no real title available?)
• ON GOOD TRIANGULATIONS IN THREE DIMENSIONS
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Verifiable implementations of geometric algorithms using finite precision arithmetic

Cited in

(14)

• Computing correct Delaunay triangulations
• Robust gift wrapping for the three-dimensional convex hull
• Correct Delaunay triangulation in the presence of inexact inputs and arithmetic
• Exact computation of Delaunay and power triangulations
• Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean \(d\)-dimensional space
• Classroom examples of robustness problems in geometric computations
• Robust Point-Location in Generalized Voronoi Diagrams
• DELAUNAY PARTITIONING IN THREE DIMENSIONS AND SEMICONDUCTOR MODELS
• ON GOOD TRIANGULATIONS IN THREE DIMENSIONS
• scientific article; zbMATH DE number 722438 (Why is no real title available?)
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• scientific article; zbMATH DE number 822231 (Why is no real title available?)
• scientific article; zbMATH DE number 5019916 (Why is no real title available?)
• A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point Arithmetic

This page was built for publication: Delaunay triangulations in three dimensions with finite precision arithmetic

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