A general approach to the analysis of controlled perturbation algorithms

DOI10.1016/j.comgeo.2011.06.001zbMath1247.65024OpenAlexW2004412712MaRDI QIDQ654290

Ralf Osbild, Michael Sagraloff, Kurt Mehlhorn

Publication date: 28 December 2011

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

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

zbMATH Keywords

algorithmorientationcontrolled perturbationfloating-point computationgeometric predicatesintersection point of three circlesnumerical robustness problemsreliable geometric computing

Mathematics Subject Classification ID

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

Related Items (3)

Analytical aspects of tie breaking ⋮ Counting solutions of a polynomial system locally and exactly ⋮ Root refinement for real polynomials using quadratic interval refinement

Uses Software

• CGAL
• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards exact geometric computation
• A geometric consistency theorem for a symbolic perturbation scheme
• Computing correct Delaunay triangulations
• A perturbation scheme for spherical arrangements with application to molecular modeling
• Efficient perturbations for handling geometric degeneracies
• The nature and meaning of perturbations in geometric computing
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Reliable and Efficient Computational Geometry Via Controlled Perturbation
• EXACT GEOMETRIC COMPUTATION USING CASCADING
• CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES
• A simple but exact and efficient algorithm for complex root isolation
• Algorithms – ESA 2004

This page was built for publication: A general approach to the analysis of controlled perturbation algorithms