

Computational Geometry
Sommersemester 2002
Lecturer:
Stefan Schirra
Lectures:
Wednesday 1315, room 308, building 03
(no lecture on the first Wednesday each month)
Wednesday 1719, room 308, building 03 is used as subsitute as announced below.
Friday 911, room 108, building 02


No lectures on 
Additional lectures on 
Wednesday, May 8 
Wednesday, May 15, 1719, room 308, building 03 
Wednesday, May 22 

Wednesday, May 29 (dies academicus) 

Wednesday, June 5 
Wednesday, June 12, 1719, room 308, building 03 
Wednesday, July 3 
Wednesday, July 10, 1719, room 308, building 03 
Purpose:
The purpose of this course is to introduce students to the
design and analysis of efficient algorithms for combinatorial
geometric problems. Topics covered include
 planesweep
 pruneandsearch
 divideandconquer
 incremental construction
 randomization
 duality and inversion
 parametric search
 convex hull algorithms in 2D and 3D
 intersection of halfspaces
 triangulations
 Voronoi diagrams and Delaunay triangulations
 lower envelopes and DavenportSchinzel sequences
 complexity of the union of simple plane figures
Audience:
computer science (Hauptstudium),
computational visualistics (Hauptstudium and master)
Prerequisites:
Basic knowledge in algorithms and data
structures (such as sorting algorithms, balanced binary search trees,
lists, and stacks), and in the analysis of algorithms using
the BigOh notation.
Reading Material
 Plane Sweep
 2D Convex Hull
Section 1.1 in [1];
There is a JavaApplet animating a version of
Graham's Scan
that performs a rotational sweep. The Applet was developed at Princeton University by Hausner and Dobkin.
 Line Segment Intersection
Chapter 2 in [1]; Section 10.7 in [9], in particular pages 735757.; Section 2.3.2 in [2]; Section 7.2.3 in [4]; Section 3.2.2 in [5]; Section VIII.4.1 in [7];
 Topological Sweep
H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. J. Comput. System Sci. 38 (1989), 165194. Corrigendum. J. Comput.
System Sci. 42 (1991), 249251.
A preceding version of this paper appeared as SRC Technical Report 009
Topologically Sweeping an Arrangement (1986).
E. Rafalin, D. Souvaine, I. Streinu. Topological sweep in degenerate cases. ALENEX 02 (2002), SanFrancisco, CA.
H. Edelsbrunner, D. Souvaine. Computing MedianofSquares Regression Lines and Guided Topological Sweep. Journal of the American Statistical Association 85 (1990), 115119.
 Prune & Search
 Stabbing Line of Vertical Line Segments
Section 15.6 in [6];
 2D Convex Hull
The quickhull algorithm is not a proper prune & search algorithm, rather a search & divide & prune algorithm.
It is discussed in Section 3.3.4 in [4];
There is also a JavaApplet animating
Quickhull.
The Applet was developed at Princeton University by Hausner and Dobkin.
 Divide & Conquer
 2D Convex Hull
Section 3.3.4 in [4]; Section 9.2 in [5]; Section 8.3.2 in [7]; Section 3.8 in [3];
 Voronoi Diagrams
Chapters 5 and 6 in [2], especially 6.4 concerning divide & conquer; Section 5 in [4]; A plane sweep algorithm for computing a Voronoi diagram is presented in Chapter 7 in [1]; Chapter 5 in [3];
VoroGlide is a nice JavaApplet
animating Voronoi diagrams, developed in Rolf Kleins former group at Fernuniversität Hagen.
 Incremental Construction
 2D Arrangements of Lines
Section 8.3 in [1]; Section 14.3 and 14.4 in [5];
 2D Convex Hull
Section 3.7 in [3];
 3D Convex Hull
Section 11.1 and 11.2 in [1]; Chapter 8 in [5]; Section 4.2.3 and 4.3 in [3];
 Randomization
 Randomized Incremental Construction (RIC)
Chapter 3 [8]; Chapter 5 in [5]; Section 9.5 in [1];
Backwards analysis is presented in Chapter 9 in [15];
 RIC of 2D Convex Hull
Chapter 9 in [15];
 RIC of 3D Convex Hull
Chapter 9 in [15]; Chapter 11 in [1]; Chapter 8 in [5];
 Geometric Transformation
 Duality
Section 8.2 in [1]; Section VIII.6.1 in [7];
 Inversion
Section VIII.6.2 in [7]; Lifting on the unit paraboloid is
breifly discussed in Section 8.5 in [1] and Section 6.5 in
[2]; See also beginning of Section 6.3 in [4]
and Section 1.7 and Chapter 13 in [6];
 Parametric Search
Michiel Smid's lecture notes Solving geometric optimization problems using parametric search;
Some Books on Computational Geometry

[1] Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
Computational Geometry: Algorithms and Applications
SpringerVerlag, second edition, 2000.


[2] Rolf Klein
Algorithmische Geometrie
AddisonWesley (in German), 1997.


[3] Joseph O'Rourke
Computational Geometry in C
Cambridge University Press, second edition, 1998.


[4] Franco P. Preparata, Michael Ian Shamos
Computational Geometry
SpringerVerlag, corrected fifth printing, 1993.


[5] JeanDaniel Boissonnat, Mariette Yvinec
Algorithmic Geometry
Cambridge University Press, 1998.


[6] Herbert Edelsbrunner
Algorithms in Combinatorial Geometry
EATCS Monographs on Theoretical Computer Science, Vol. 10
SpringerVerlag, 1987.
[7] Kurt Mehlhorn
Data Structures and Algorithms 3:
MultiDimensional Searching and Computational Geometry
EATCS Monographs on Theoretical Computer Science, Vol. 3
SpringerVerlag, 1984.
[8] Ketan Mulmuley
Computational Geometry: An Introduction Through Randomized Algorithms
PrenticeHall, 1993.


[9] Kurt Mehlhorn, Stefan Näher
The LEDA Platform of Combinatorial and Geometric Computing
Cambridge University Press, 1999.
[10] Jürg Nievergelt, Klaus H. Hinrichs
Algorithms and Data Structures: With Applications to Graphics and Geometry
PrenticeHall, 1993.
[11] JörgRüdiger Sack, Jorge Urrutia (Editors)
Handbook on Computational Geometry
Elsevier, 2000.
[12] Jacob E. Goodman, Joseph O'Rourke (Editors)
Handbook of Discrete and Computational Geometry
CRC Press, 1997.
[13] János Pach, Pankaj K. Agarwal
Combinatorial Geometry
John Wiley & Sons, 1995.
[14] Micha Sharir, Pankaj K. Agarwal
DavenportSchinzel Sequences and Their Geometric Applications
Cambridge University Press, 1995.
[15] János Pach (Ed.)
New Trends in Discrete and Computational Geometry
SpringerVerlag, 1993.

