Classroom examples of robustness problems in geometric computations

DOI10.1016/j.comgeo.2007.06.003zbMath1135.65311OpenAlexW2148713284WikidataQ56017902 ScholiaQ56017902MaRDI QIDQ2479475

Kurt Mehlhorn, Lutz Kettner, Sylvain Pion, Chee-Keng Yap, Stefan Schirra

Publication date: 26 March 2008

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

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

zbMATH Keywords

algorithmsnumerical examplesimplementationcomputational geometryconvex hullsDelaunay triangulationsnumerical robustness problemsfloating-point geometry

Mathematics Subject Classification ID

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

Related Items

Faster geometric algorithms via dynamic determinant computation, Simple floating-point filters for the two-dimensional orientation problem, Far-field reflector problem and intersection of paraboloids, Fourth- and Higher-order Interface Tracking Via Mapping and Adjusting Regular Semianalytic sets Represented by Cubic Splines, Smoothing the Gap Between NP and ER, Boolean algebra of two-dimensional continua with arbitrarily complex topology, Designing and proving correct a convex hull algorithm with hypermaps in Coq, Convex-hull algorithms: implementation, testing, and experimentation, Design of the CGAL 3D spherical kernel and application to arrangements of circles on a sphere, Certifying algorithms, Exact Fast Parallel Intersection of Large 3-D Triangular Meshes, Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity, Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order, A robust algorithm for geometric predicate by error-free determinant transformation, Of What Use Is Floating-Point Arithmetic in Computational Geometry?, Much Ado about Zero, Exact Computation for Existence of a Knot Counterexample

Uses Software

• CGAL
• LEDA
• Qhull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An acyclicity theorem for cell complexes in d dimensions
• Another efficient algorithm for convex hulls in two dimensions
• Delaunay triangulations in three dimensions with finite precision arithmetic
• A perturbation scheme for spherical arrangements with application to molecular modeling
• Computing convex hull in a floating point arithmetic
• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• Recent progress in exact geometric computation
• Applications of random sampling in computational geometry. II
• Constructing strongly convex approximate hulls with inaccurate primitives
• An efficient algorithm for determining the convex hull of a finite planar set
• WALKING IN A TRIANGULATION
• The quickhull algorithm for convex hulls
• NUMERICAL STABILITY OF ALGORITHMS FOR 2D DELAUNAY TRIANGULATIONS
• On the design of CGAL a computational geometry algorithms library
• Backward Error Analysis in Computational Geometry
• Pitfalls in Computation, or why a Math Book isn't Enough