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):

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

URL of the conference:


URL for downloading the paper:


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
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)
Christine Kiesel
Created
08/14/2006 12:41:29 PM
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