de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Reliable and Efficient Computational Geometry Via Controlled Perturbation

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45146

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45332

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-23D5-3
Zusammenfassung
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).