[Research Groups | Research | Teaching | General Information | Home | Search]

Research Groups

Research

Teaching

General Information

Home

School of Computer Science

 

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.



  • Webmaster  -