A general approach to the analysis of controlled perturbation algorithms

DOI10.1016/J.COMGEO.2011.06.001zbMATH Open1247.65024OpenAlexW2004412712MaRDI QIDQ654290FDOQ654290

Authors K. Mehlhorn, Ralf Osbild, Michael Sagraloff 

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)

Recommendations

• Reliable and Efficient Computational Geometry Via Controlled Perturbation
• Controlled Perturbation for Certified Geometric Computing with Fixed-Precision Arithmetic
• Controlled perturbation for Delaunay triangulations
• Reliable and Efficient Geometric Computing
• Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order

Cites Work

• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A geometric consistency theorem for a symbolic perturbation scheme
• A perturbation scheme for spherical arrangements with application to molecular modeling
• A simple but exact and efficient algorithm for complex root isolation
• Algorithms – ESA 2004
• CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES
• Computing correct Delaunay triangulations
• Controlled perturbation for Delaunay triangulations
• EXACT GEOMETRIC COMPUTATION USING CASCADING
• Efficient perturbations for handling geometric degeneracies
• Reliable and Efficient Computational Geometry Via Controlled Perturbation
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The nature and meaning of perturbations in geometric computing
• Towards exact geometric computation

Cited In (9)

• Controlled perturbation of sets of line segments in \(\mathbb R^2\) with smart processing order
• CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES
• Counting solutions of a polynomial system locally and exactly
• Precision Control for Generalized Pattern Search Algorithms with Adaptive Precision Function Evaluations
• Root refinement for real polynomials using quadratic interval refinement
• Controlled perturbation for Delaunay triangulations
• Controlled perturbation for arrangements of circles
• Reliable and Efficient Geometric Computing
• Analytical aspects of tie breaking

Uses Software

• CGAL
• LEDA

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

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