[Arbeitsgruppen | Forschung | Studium & Lehre | Allgemeines | Home | Suche | English]

Arbeitsgruppen und Lehrstühle

Forschung

Studium und Lehre

Allgemeines

Home

Suche

Fakultät für Informatik

 
 

Robust Geometric Computing

Sommersemester 2019

Stefan Schirra

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 floating-point arithmetic for real arithmetic and uses real-world 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 well-known 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.

polygon coordinates
 



RGC moodle

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):

Polygon 4 5 6 7
Queries 4 5 6 7
Answers 4 5 6 7

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 Floating-Point 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 Error-Free Transformations

Lecture 7
16 Floating-Point 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 Point-in-Polygon Strategies and Pitfalls

Lecture 11
23 Division-Free 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 Degree-Driven Computation
29 Data Normalization
30 Structural Filtering
31 Degeneracies
32 Topology-Oriented Approaches

Lecture 16
32 Topology-Oriented Approaches
33 Symbolic Perturbation

Lecture 17
34 Controlled Perturbation



Webmaster  -