MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Funke, Stefan
Klein, Christian
Mehlhorn, Kurt
Schmitt, Susanne		dblp
dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
FKMS2005
Title, Booktitle
Title*:
Controlled Perturbation for Delaunay Triangulations
Booktitle*:
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Event, URLs
Conference URL::
Downloading URL:
http://doi.acm.org/10.1145/1070432.1070582
Event Address*:
Vancouver, Canada
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
23 January 2005
Event End Date:
25 January 2005
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1047-1056
Year*:
2005
VG Wort Pages:
43
ISBN/ISSN:
0-89871-585-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Most geometric algorithms are idealistic in the sense that they are designed
for the Real-RAM model of computation and for inputs in general
position. Real inputs may be degenerate and floating point arithmetic is
only an approximation of real arithmetic.
Perturbation replaces an input by a nearby input which is (hopefully)
in general position and on which the algorithm can be run with floating point
arithmetic. Controlled perturbation as proposed by Halperin et al. calls for
more: control over the amount of perturbation needed for a given precision of
the floating point system. Or conversely, a control over the precision needed
for a given amount of perturbation. Halperin et al.~gave controlled
perturbation schemes for arrangements of polyhedral surfaces, spheres, and
circles. We extend their work and point out that controlled perturbation is a
general scheme for converting idealistic algorithms into algorithms which can
be executed with floating point arithmetic. We also show how to use controlled
perturbation in the context of randomized geometric algorithms without
deteriorating the running time. Finally, we give concrete schemes for planar
Delaunay triangulations and convex hulls and Delaunay triangulations in
arbitrary dimensions. We analyze the relation between the
perturbation amount and the precision of the floating point system. We also
report about experiments with a planar Delaunay diagram algorithm.
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{FKMS2005,
AUTHOR = {Funke, Stefan and Klein, Christian and Mehlhorn, Kurt and Schmitt, Susanne},
 TITLE = {Controlled Perturbation for Delaunay Triangulations},
 BOOKTITLE = {Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)},
 PUBLISHER = {SIAM},
 YEAR = {2005},
 PAGES = {1047--1056},
 ADDRESS = {Vancouver, Canada},
 ISBN = {0-89871-585-7},
}

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)
Christian Klein		Created
02/08/2005 05:39:03 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Anja Becker
Christine Kiesel
Tamara Hausmann
Christian Klein
Christian Klein		Edit Dates
05.02.2008 14:19:29
29.09.2006 07:39:01
13.06.2006 12:03:59
11/09/2005 03:49:09 PM
25.04.2005 18:35:33