

No class on Mon, Jun 24 and Thu, Jun 27!
Content:
[CG Impact Task Force]
Geometric algorithms are usually described assuming that input
data is in general position and that exact real arithmetic
provides reliable geometric primitives. Often an implementer
substitutes floatingpoint arithmetic for real arithmetic and
uses realworld data, which might be degenerate by accident
or design. Hence, the correctness proof of the mathematical
algorithm does not extend to the program, and the program
can fail on seemingly appropriate input data. This is the wellknown
problem of "nonrobustness" in geometric computing
and the topic of this course.
This is not a pure theory course: We have to struggle with the details
of actual computer systems, in particular with computer arithmetic
and the C++ programming language.
Hence, programming skills are a must.
However, this is not a course in practical computer science either:
We shall study some foundations of computational and algebraic
geometry as well as numerical computations.
Homework Exercises:
Exercise Set 1
Set 2
Set 3
Set 4
Set 5
Set 4 will be discussed on Thursday, May 23. Deadline for
submissions is Tuesday, May 21, noon.
The following table provides three test sets consisting of polygon
data (given as sequence of vertex coordinates), query points and corresponding
locations ( 1 = inside, 0 = outside):
Slides:
Lecture 1
01 Computational Geometry
02 Theory & Practice in Computational Geometry
03 Precision Issues in Computational Geometry
04 Numerical Analysis & Computational Geometry
Lecture 2
05 Polygonization Challenge
06 FloatingPoint Arithmetic
Lecture 3
07 Epsilon Tolerances
08 Sustainable Approaches
09 Geometric Predicates
Lecture 4
10 Orientation Predicate
11 Exact Arithmetic
12 Exact Decisions Computation
Lecture 5
13 Rounding Error Bounds
Lecture 6
14 Arithmetic Filters
15 ErrorFree Transformations
Lecture 7
16 FloatingPoint Summation
17 Expansions
Lecture 8
18 Lazy Adaptive Evaluation
19 Computational Geometry Software Libraries
Lecture 9
20 More on Orientation Predicate
21 Representation and Model Approach


Lecture 10
22 PointinPolygon Strategies and Pitfalls
Lecture 11
23 DivisionFree Computation
24 Arrangements of Lines
Lecture 12
25 Algebraic Numbers
Lecture 13
26 Real Algebraic Computing
Lecture 14
27 Zero Separation Bounds
Lecture 15
28 DegreeDriven Computation
29 Data Normalization
30 Structural Filtering
31 Degeneracies
32 TopologyOriented Approaches
Lecture 16
32 TopologyOriented Approaches
33 Symbolic Perturbation
Lecture 17
34 Controlled Perturbation
Lecture 18
35 Epsilon Geometry
36 Geometric Rounding
Lecture 19
37 Zero Rewriting
38 Convex Hull Computation
Summary
All Slides

