Robust Geometric Computing Sommersemester 2010 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 uns 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).

Prüfung:
mündlich

Übungen:
  1. Übung
  2. Übung
  3. Übung

Slides:
  0.   Introduction
  1.   The Robustness Problem in Computational Geometry
  2.   Numerical Analysis and Computational Geometry
  3.   A Brief Introduction to Computer Arithmetic
  4.   A Little Bit about Rounding Errors
  5.   A Comprehensive Case Study on How and Why Geometric Algorithms Fail
  6.   Geometric Computations and Geometric Primitives
  7.   Exact Arithmetic Computation
  8.   Exact Decisions Computation
  9.   Arithmetic Filters
10.   Arithmetic Filters II
11.   Epsilon Tweaking
12.   Computational Geometry Software Libraries
13.   Generic Geometric Computation
14.   Error-Free Transformations with Floating-Point Numbers
15.   Floating-Point Expansions
16.   Lazy Adaptive Evaluation
17.   Determinants
18.   Homogeneous Coordinates
19.   Approximate versus Exact Planar Convex Hull Computation
20.   Dealing with Degeneracies
21.   Topology-Oriented Approaches
22.   Computing with Real Algebraic Numbers
23.   Arrangements of Circular Arcs