Wednesday 13-15, room 308, building 03
(no lecture on the first Wednesday each month)
Wednesday 17-19, room 308, building 03 is used as subsitute as announced below.
Friday 9-11, room 108, building 02
|No lectures on
||Additional lectures on
|Wednesday, May 8
||Wednesday, May 15, 17-19, room 308, building 03
|Wednesday, May 22
|Wednesday, May 29 (dies academicus)
|Wednesday, June 5
||Wednesday, June 12, 17-19, room 308, building 03
|Wednesday, July 3
||Wednesday, July 10, 17-19, room 308, building 03
The purpose of this course is to introduce students to the
design and analysis of efficient algorithms for combinatorial
geometric problems. Topics covered include
- incremental construction
- duality and inversion
- parametric search
- convex hull algorithms in 2D and 3D
- intersection of halfspaces
- Voronoi diagrams and Delaunay triangulations
- lower envelopes and Davenport-Schinzel sequences
- complexity of the union of simple plane figures
computer science (Hauptstudium),
computational visualistics (Hauptstudium and master)
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 Big-Oh notation.
- Plane Sweep
- 2D Convex Hull
Section 1.1 in ;
There is a Java-Applet animating a version of
that performs a rotational sweep. The Applet was developed at Princeton University by Hausner and Dobkin.
- Line Segment Intersection
Chapter 2 in ; Section 10.7 in , in particular pages 735-757.; Section 2.3.2 in ; Section 7.2.3 in ; Section 3.2.2 in ; Section VIII.4.1 in ;
- Topological Sweep
H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. J. Comput. System Sci. 38 (1989), 165-194. Corrigendum. J. Comput.
System Sci. 42 (1991), 249-251.
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), San-Francisco, CA.
H. Edelsbrunner, D. Souvaine. Computing Median-of-Squares Regression Lines and Guided Topological Sweep. Journal of the American Statistical Association 85 (1990), 115-119.
- Prune & Search
- Stabbing Line of Vertical Line Segments
Section 15.6 in ;
- 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 ;
There is also a Java-Applet animating
The Applet was developed at Princeton University by Hausner and Dobkin.
- Divide & Conquer
- 2D Convex Hull
Section 3.3.4 in ; Section 9.2 in ; Section 8.3.2 in ; Section 3.8 in ;
- Voronoi Diagrams
Chapters 5 and 6 in , especially 6.4 concerning divide & conquer; Section 5 in ; A plane sweep algorithm for computing a Voronoi diagram is presented in Chapter 7 in ; Chapter 5 in ;
VoroGlide is a nice Java-Applet
animating Voronoi diagrams, developed in Rolf Kleins former group at Fernuniversität Hagen.
- Incremental Construction
- 2D Arrangements of Lines
Section 8.3 in ; Section 14.3 and 14.4 in ;
- 2D Convex Hull
Section 3.7 in ;
- 3D Convex Hull
Section 11.1 and 11.2 in ; Chapter 8 in ; Section 4.2.3 and 4.3 in ;
- Randomized Incremental Construction (RIC)
Chapter 3 ; Chapter 5 in ; Section 9.5 in ;
Backwards analysis is presented in Chapter 9 in ;
- RIC of 2D Convex Hull
Chapter 9 in ;
- RIC of 3D Convex Hull
Chapter 9 in ; Chapter 11 in ; Chapter 8 in ;
- Geometric Transformation
Section 8.2 in ; Section VIII.6.1 in ;
Section VIII.6.2 in ; Lifting on the unit paraboloid is
breifly discussed in Section 8.5 in  and Section 6.5 in
; See also beginning of Section 6.3 in 
and Section 1.7 and Chapter 13 in ;
- Parametric Search
Michiel Smid's lecture notes Solving geometric optimization problems using parametric search;
Some Books on Computational Geometry
 Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf|
Computational Geometry: Algorithms and Applications
Springer-Verlag, second edition, 2000.
 Rolf Klein|
Addison-Wesley (in German), 1997.
 Joseph O'Rourke|
Computational Geometry in C
Cambridge University Press, second edition, 1998.
 Franco P. Preparata, Michael Ian Shamos|
Springer-Verlag, corrected fifth printing, 1993.
 Jean-Daniel Boissonnat, Mariette Yvinec|
Cambridge University Press, 1998.
 Herbert Edelsbrunner
Algorithms in Combinatorial Geometry
EATCS Monographs on Theoretical Computer Science, Vol. 10
 Kurt Mehlhorn
Data Structures and Algorithms 3:
Multi-Dimensional Searching and Computational Geometry
EATCS Monographs on Theoretical Computer Science, Vol. 3
 Ketan Mulmuley
Computational Geometry: An Introduction Through Randomized Algorithms
 Kurt Mehlhorn, Stefan Näher|
The LEDA Platform of Combinatorial and Geometric Computing
Cambridge University Press, 1999.
 Jürg Nievergelt, Klaus H. Hinrichs
Algorithms and Data Structures: With Applications to Graphics and Geometry
 Jörg-Rüdiger Sack, Jorge Urrutia (Editors)
Handbook on Computational Geometry
 Jacob E. Goodman, Joseph O'Rourke (Editors)
Handbook of Discrete and Computational Geometry
CRC Press, 1997.
 János Pach, Pankaj K. Agarwal
John Wiley & Sons, 1995.
 Micha Sharir, Pankaj K. Agarwal
Davenport-Schinzel Sequences and Their Geometric Applications
Cambridge University Press, 1995.
 János Pach (Ed.)
New Trends in Discrete and Computational Geometry