MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mehlhorn, Kurt
Osbild, Ralf
Sagraloff, Michael		dblp
dblp
dblp
Editor(s):
Bugliesi, Michele
Preneel, Bart
Sassone, Vladimir
Wegener, Ingo		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Bugliesi, Michele
Preneel, Bart
Sassone, Vladimir
Wegener, Ingo
BibTeX cite key*:
MOS06
Title, Booktitle
Title*:
Reliable and Efficient Computational Geometry Via Controlled Perturbation
Booktitle*:
Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 July 2006
Event End Date:
14 July 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4051
Number:
Month:
Pages:
299-310
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
3-540-35904-4
Sequence Number:
DOI:
10.1007/11786986_27
Note, Abstract, ©
(LaTeX) 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).
URL for the Abstract:
http://dx.doi.org/10.1007/11786986_27
Download
Access Level:
Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MOS06,
AUTHOR = {Mehlhorn, Kurt and Osbild, Ralf and Sagraloff, Michael},
 EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimir and Wegener, Ingo},
 TITLE = {Reliable and Efficient Computational Geometry Via Controlled Perturbation},
 BOOKTITLE = {Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4051},
 PAGES = {299--310},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Venice, Italy},
 ISBN = {3-540-35904-4},
 DOI = {10.1007/11786986_27},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel		Created
08/14/2006 12:41:29
Revisions
5.
4.
3.
2.
1.		Editor(s)
Anja Becker
Christine Kiesel
Ralf Osbild
Christine Kiesel
Christine Kiesel		Edit Dates
06.02.2008 09:47:20
28.03.2007 16:14:52
07.03.2007 16:41:30
07.02.2007 18:48:22
04.10.2006 07:53:18