Item

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.