MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kettner, Lutz
Mehlhorn, Kurt
Pion, Sylvain
Schirra, Stefan
Yap, Chee		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Pion, Sylvain
Schirra, Stefan
Yap, Chee
Editor(s):
Albers, Susanne
Radzik, Tomasz		dblp
dblp
Not MPII Editor(s):
Albers, Susanne
Radzik, Tomasz
BibTeX cite key*:
Kettner2004Classroom
Title, Booktitle
Title*:
Classroom Examples of Robustness Problems in Geometric Computations
Booktitle*:
ESA 2004: 12th Annual European Symposium on Algorithms
Event, URLs
Conference URL::
Downloading URL:
http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3221&spage=702
Event Address*:
Bergen, Norway
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
14 September 2004
Event End Date:
17 September 2004
Publisher
Name*:
Springer
URL:
http://springeronline.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3221
Number:
Month:
September
Pages:
702-713
Year*:
2004
VG Wort Pages:
17
ISBN/ISSN:
3-540-23025-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
The algorithms of computational geometry are designed for a
machine model with exact real arithmetic. Substituting floating point
arithmetic for the assumed real arithmetic may cause implementations to
fail. Although this is well known, there is no comprehensive documentation of
what can go wrong and why.
In this extended abstract, we study a simple
incremental algorithm for planar convex hulls and give examples which make
the algorithm fail in all possible ways.
We also show how to construct failure-examples
semi-systematically and discuss the geometry of the floating point
implementation of the orientation predicate. We hope that our work will be
useful for teaching computational geometry. The full
paper is available
at~\url{www.mpi-sb.mpg.de/~mehlhorn/ftp/ClassRoomExamples.ps}. It contains
further examples, more theory, and color pictures. We strongly recommend to read
the
full paper instead of this extended abstract.
URL for the Abstract:
http://www.mpi-sb.mpg.de/~kettner/pub/nonrobust_esa_04_a.html
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/esa/esa2004.html#KettnerMPSY04
http://www.mpi-sb.mpg.de/~kettner/proj/NonRobust/
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{Kettner2004Classroom,
AUTHOR = {Kettner, Lutz and Mehlhorn, Kurt and Pion, Sylvain and Schirra, Stefan and Yap, Chee},
 EDITOR = {Albers, Susanne and Radzik, Tomasz},
 TITLE = {Classroom Examples of Robustness Problems in Geometric Computations},
 BOOKTITLE = {ESA 2004: 12th Annual European Symposium on Algorithms},
 PUBLISHER = {Springer},
 YEAR = {2004},
 VOLUME = {3221},
 PAGES = {702--713},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bergen, Norway},
 MONTH = {September},
 ISBN = {3-540-23025-4},
}

Entry last modified by Anja Becker, 01/16/2008
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)
Lutz Kettner		Created
09/22/2004 11:09:10
Revisions
9.
8.
7.
6.
5.		Editor(s)
Anja Becker
Ulrich Meyer
Ulrich Meyer
Christine Kiesel
Christine Kiesel		Edit Dates
16.01.2008 13:35:50
03/21/2007 03:35:40 PM
03/21/2007 03:32:11 PM
29.09.2006 09:29:05
13.06.2006 12:35:15