Computational Geometry Sommersemester 2002 Lecturer: Stefan Schirra Lectures: 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

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

• plane-sweep
• prune-and-search
• divide-and-conquer
• 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 Davenport-Schinzel 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 Big-Oh notation.

Reading Material

• Plane Sweep
  
  
  • 2D Convex Hull
    
    Section 1.1 in [1];
    
    There is a Java-Applet 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 735-757.; 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), 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 [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 Java-Applet 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 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 [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 Springer-Verlag, second edition, 2000.
	[2] Rolf Klein Algorithmische Geometrie Addison-Wesley (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 Springer-Verlag, corrected fifth printing, 1993.
	[5] Jean-Daniel Boissonnat, Mariette Yvinec Algorithmic Geometry Cambridge University Press, 1998.
	[6] Herbert Edelsbrunner Algorithms in Combinatorial Geometry EATCS Monographs on Theoretical Computer Science, Vol. 10 Springer-Verlag, 1987. [7] Kurt Mehlhorn Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry EATCS Monographs on Theoretical Computer Science, Vol. 3 Springer-Verlag, 1984. [8] Ketan Mulmuley Computational Geometry: An Introduction Through Randomized Algorithms Prentice-Hall, 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 Prentice-Hall, 1993. [11] Jörg-Rü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 Davenport-Schinzel Sequences and Their Geometric Applications Cambridge University Press, 1995. [15] János Pach (Ed.) New Trends in Discrete and Computational Geometry Springer-Verlag, 1993.