Robust Geometric Computing Wintersemester 2007/08 Stefan Schirra Stundenplan

Inhalt: Geometrische Algorithmen werden meist unter der Annahme entworfen, dass exakte reelle Arithmetik zur Verfügung steht. Beim Implemtieren der entworfenen Algorithmen wird aber oft einfach unreflektiert rundungsfehlerbehaftete Gleitkommaarithmetik als Ersatz für exakte reelle Arithmetik benutzt, was dann oft zu inkonsistenten Entscheidungen und daraus resultierend fehlerhaften Berechungen und sogar Programmabstürzen führt. In der Vorlesung werden solche Probleme analysiert und Methoden zum verifizierten, verlässlichen und dennoch effizienten geometrischen Rechnen vorgestellt. Wir betrachten dabei sowohl rationale geometrische Probleme als auch algebraische. Insbesondere werden wir das Paradigma des exakten geometrischen Rechnens genauer anschauen.

Voraussetzungen: Grundkenntnisse in Algorithmischer Geometrie (die man sich aber auch im Verlaufe der Vorlesung im Selbststudium aneignen kann).

Erwerb der Leistungspunkte: mündliche Prüfung

Slides: (Access   User Name: firstname.lastname Password:your matriculation number)
  0.   Introduction (white bg)
  1.   The Robustness Problem in Computational Geometry (white bg)
  2.   A Brief Introduction to Computer Arithmetic (white bg)
  3.   A Little Bit about Rounding Errors (white bg)
  4.   A Comprehensive Case Study on How and Why Geometric Algorithms Fail (white bg)
  5.   Numerical Analysis and Computational Geometry (white bg)
  6.   Geometric Computation and Geometric Primitives (white bg)
  7.   Exact Rational Arithmetic (white bg)
  8.   Exact Geometric Computation Paradigm (white bg)
  9.   Error Bound Computation (white bg)
10.   Arithmetic Filters (white bg)
11.   Epsilon Tweaking (white bg)
12.   Error-Free Transformations with Floating-Point Numbers (white bg)
13.   Floating-Point Expansions (white bg)
14.   Lazy Adaptive Evaluation (white bg)
15.   Determinants (white bg)
16.   Homogeneous Coordinates (white bg)
17.   Computational Geometry Software Libraries (white bg)
18.   Approximate versus Exact Planar Convex Hull Computation (white bg)
19.   Dealing with Degeneracies (white bg)
20.   Arrangements of Lines (white bg)
21.   Topology-Oriented Approach (white bg)
22.   Computing with Real Algebraic Numbers (white bg)
23.   Plane Algebraic Curves (white bg)
24.   Arrangements of Circular Arcs (white bg)

Übungen:
   Exercise Set 1
   Exercise Set 2
   Exercise Set 3
   Exercise Set 4

Literaturhinweise: Es gibt noch kein Lehrbuch zu diesem Thema. K. Mehlhorn und C. Yap schreiben zur Zeit an einem Buch zu Robust Geometric Computation. Die Bücher von Langetepe und Zachmann über Geometric Data Structures for Computer Graphics und von Ericson über Real Time Collision Detection enthalten jeweils ein Kapitel zum Thema der Vorlesung.