Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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