Delaunay triangulation of imprecise points in linear time after preprocessing

DOI10.1016/j.comgeo.2008.12.007zbMath1177.65037OpenAlexW2041094480WikidataQ56970222 ScholiaQ56970222MaRDI QIDQ1037646

Maarten Löffler, Jack Scott Snoeyink

Publication date: 16 November 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.12.007

zbMATH Keywords

computational geometryminimum spanning treeDelaunay triangulationGabriel graphdata imprecision

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (11)

Fréchet Distance for Uncertain Curves ⋮ Minimizing the diameter of a spanning tree for imprecise points ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ Unnamed Item ⋮ The Most Likely Object to be Seen Through a Window ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ COMPUTING THE DISCRETE FRÉCHET DISTANCE WITH IMPRECISE INPUT ⋮ Data imprecision under \(\lambda\)-geometry model ⋮ The maximal distance between imprecise point objects ⋮ Computing the Fréchet distance between uncertain curves in one dimension ⋮ Preprocessing Ambiguous Imprecise Points

Uses Software

• CGAL
• LEDA
• Triangle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two design principles of geometric algorithms in finite-precision arithmetic
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Triangulating input-constrained planar point sets
• Triangulating a simple polygon in linear time
• Finding the medial axis of a simple polygon in linear time
• Dense packings of congruent circles in a circle
• Delaunay refinement algorithms for triangular mesh generation
• Structural tolerance and Delaunay triangulation
• Correct Delaunay triangulation in the presence of inexact inputs and arithmetic
• Constructing strongly convex approximate hulls with inaccurate primitives
• Almost-Delaunay simplices: Robust neighbor relations for imprecise 3D points using CGAL
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Preprocessing Imprecise Points and Splitting Triangulations
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract]
• Numerical Software with Result Verification
• Approximating Largest Convex Hulls for Imprecise Points

This page was built for publication: Delaunay triangulation of imprecise points in linear time after preprocessing