b'@inproceedings{MOS06,'b'\nTITLE = {Reliable and Efficient Computational Geometry Via Controlled Perturbation},\nAUTHOR = {Mehlhorn, Kurt and Osbild, Ralf and Sagraloff, Michael},\nEDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimir and Wegener, Ingo},\nLANGUAGE = {eng},\nISBN = {3-540-35904-4},\nLOCALID = {Local-ID: C1256428004B93B8-1C44F76383A124E7C12571CA003ABB0D-MOS06},\nPUBLISHER = {Springer},\nYEAR = {2006},\nDATE = {2006},\nABSTRACT = {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 $\\delta$-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 $\\delta$ 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 $\\delta$ 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).},\nBOOKTITLE = {Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I},\nPAGES = {299--310},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {4051},\n}\n'