English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Classroom Examples of Robustness Problems in Geometric Computations

Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., & Yap, C. (2004). Classroom Examples of Robustness Problems in Geometric Computations. In Algorithms – ESA 2004: 12th Annual European Symposium (pp. 702-713). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kettner, Lutz1, Author           
Mehlhorn, Kurt1, Author           
Pion, Sylvain1, Author           
Schirra, Stefan1, Author           
Yap, Chee1, Author           
Albers, Susanne1, Editor           
Radzik, Tomasz, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2005-04-222004
 Publication Status: Issued
 Pages: -
 Publishing info: Berlin, Germany : Springer
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 231814
Other: Local-ID: C1256428004B93B8-433D199DFE8DDF4DC1256F170032471A-Kettner2004Classroom
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Bergen, Norway
Start-/End Date: 2004-09-14

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms – ESA 2004: 12th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 702 - 713 Identifier: ISBN: 3-540-23025-4

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -