English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Reliable and Efficient Computational Geometry Via Controlled Perturbation

MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45146

Osbild,  Ralf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45332

Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., Osbild, R., & Sagraloff, M. (2006). Reliable and Efficient Computational Geometry Via Controlled Perturbation. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I (pp. 299-310). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-23D5-3
Abstract
Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic may fail. Controlled perturbation replaces an input x by a random nearby in the δ-neighborhood of x and then runs the floating point version of the idealistic algorithm on . The hope is that this will produce the correct result for with constant probability provided that δ is small and the precision L of the floating point system is large enough. We turn this hope into a theorem for a large class of geometric algorithms and describe a general methodology for deriving a relation between δ and L. We exemplify the usefulness of the methodology by examples. Partially supported by the IST Programme of the EU under Contract No IST-006413, Algorithms for Complex Shapes (ACS).