 [Arbeitsgruppen | Forschung | Studium & Lehre | Allgemeines | Home | Suche | English] # Robust Geometric Computing

Sommersemester 2019

Stefan Schirra

No class on Mon, Jun 24 and Thu, Jun 27!

Content:

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 Lecture 18 35 Epsilon Geometry 36 Geometric Rounding Lecture 19 37 Zero Rewriting 38 Convex Hull Computation     Summary All Slides

Webmaster  -