Robust Geometric Computing

Wintersemester 2006/07

Stefan Schirra

No lecture on

Oct 13, 2006

Syllabus: Algorithms in computational geometry are usually designed under the assumption that basic operations on real numbers are performed exactly and in constant time. In practice, however, hardware-supported floating-point arithmetic is often used as a straightforward replacement. And floating-point arithmetic is inherently imprecise and might lead to inconsistent decisions and as a consequence lead to disatrous effects: algorithms, whose correctness has been proved under the assumption of exact arithmetic, might compute incorrect results (like the convex hulls in the figures above), loop, or simply crash.

segmentation fault bus error
In this course we will have a look at approaches to overcome such precision caused robustness problems. In particular, we will study the exact geometric computation paradigm. This part of the course will be close to Implementation of Geometric Algorithms taught in WiSe 2002/03. However, we will look at non-linear geometric problems involving algebraic numbers as well and the related part of the course will be close to Algebraic Algorithmic Geometry taught in SoSe 2004. Therefore, you cannot bring in this course together with any of the two above.
The course will be taught in German unless there is a request for teaching it in English and all participants agree on this. Slides, however, will be in English.

Prerequisites: Basics in computational geometry (you can learn that on the fly, of course).

Slides:
  0.   Introduction
  1.   The Robustness Problem in Computational Geometry
  2.   A Brief Introduction to Computer Arithmetic
  3.   A Comprehensive Case Study on How and Why Geometric Algorithms Fail
  4.   Numerical Analysis and Computational Geometry
  5.   Geometric Computation and Geometric Primitives    Bit Inspection
  6.   Exact Geometric Computation Paradigm
  7.   Error Bound Computation
  8.   Arithmetic Filters    (Supplement)
  9.   Floating-Point Expansions
10.   Lazy Adaptive Evaluation
11.   Homogeneous Coordinates
12.   Epsilon Tweaking
13.   Computational Geometry Software Libraries
14.   Monique Teillaud's course on CGAL
15.   Experimental Algorithmics
16.   Approximate versus Exact Convex Hull Computation in the Plane
17.   Topology-oriented Approaches
18.   Arrangements of Lines
19.   Dealing with Degeneracies
20.   Computing with Real Algebraic Numbers
21.   Determinants
22.   Linearization

Robust Geometric Computing (8up mit weissem Hintergrund)

Homework Exercises:
--1.-- --2.--

Links:
Companion page to classroom examples

Webmaster -