Computer Science Department


Computational Geometry


Prof. Micha Sharir

Fall 2000, Wed 7-9 pm; Room: 102

The course is a basic course in computational geometry. It assumes basic knowledge in algorithms, data structures, complexity, etc. It also assumes familiarity with basic geometric concepts and facts (in the plane and in higher dimensions).

There is no textbook that covers all the material given in the course, but a large portion of it is covered in the book:

De Berg, van Kreveld, Overmars and Schwarzkopf,
Computational Geometry, Algorithms and Applications (1st edition: 1997; 2nd edition: 2000).

Additional material will be distributed or given a reference to, as needed.
One may also consult the books

  • Preparata and Shamos, 
    Computational Geometry, An Introduction (1985)
    (the first textbook on the subject, somewhat outdated)
  • Edelsbrunner, 
    Algorithms in Combinatorial Geometry (1987)
    (another old and slightly more advanced textbook)
  • Mehlhorn, 
    Data Structures and Algorithms, 3: Multidimensional Searching and Computational Geometry (1983)
    (oldest book, not easy to read)
  • Mulmuley, 
    Computational Geometry: An Introduction Through Randomized Algorithms (1993)
    (uses very special approach)
  • O'Rourke, 
    Computational Geometry in C (1994)
    (elementary, practically oriented; has lots of code)
  • Boissonnat and Yvinec, 
    Algorithmic Geometry (1998)
    (another `modern' textbook)

Course requirements

Final exam and a few (about four--five) assignments during the semester. Assignments will be graded and will comprise part (about 20 percent) of the final grade. -----

The syllabus of the course

(1) Introduction:

  • Motivation, Goals, Models of Computations
  • Convex hull algorithms as an example
  • Robustness and degeneracies

(2) Convex Hull Algorithms:

  • Properties of convex sets and convex hulls
  • Simple-minded algorithms: Gift wrapping
  • Graham's Walk; analysis
  • Divide-and-Conquer approaches
  • Average case behavior
  • Applications of convex hulls: width; diameter; normal diagram
  • Convex hulls in higher dimensions
  • Convex polyhedra, Euler's formula, polyhedra in 3-D
  • On the size of convex hulls in higher dimensions; general bounds
  • Randomized convex hull algorithms
  • Lower bounds

(3) The Sweeping Paradigm:

  • An example: Detecting intersections among n line segments
  • (Application: testing a polygon for simplicity)
  • Other examples: Intersection detection for monotone objects
  • Nearest neighbors
  • Batch point location
  • Planar maps; the DCEL data structure
  • Calculating the intersection of polygonal regions and overlaying planar maps

(4) Point Location:

  • Problem definition
  • General parameters: Preprocessing, Space, Query time
  • Naive solution using sweeping
  • Kirkpatrick's sequence of maps method
  • Persistent search trees
  • Randomized incremental method

(5) Intersection Problems and Linear Programming:

  • Duality
  • Intersection of n half-planes; dual formulation as a convex hull problem
  • Intersection of n half-spaces; dual formulation
  • Linear Programming in two and three dimensions in linear time; related problems
  • Megiddo's algorithm; Randomized incremental algorithm and higher dimensions
  • Applications (smallest enclosing balls)

(6) Voronoi Diagrams:

  • Nearest neighbor searching problems
  • Voronoi diagrams: definitions and basic properties
  • Delaunay triangulation
  • Calculation of the diagram for a set of points
  • Randomized incremental construction
  • Applications: nearest neighbor searching; post-office problem; Euclidean minimum spanning trees; triangulation; motion planning for a disc
  • Fortune's line-sweeping algorithm
  • Extensions: Non-point sites, k-nearest neighbor diagrams; diagrams in higher dimensions

(7) Range Queries and Multidimensional Data Structures:

  • Two-dimensional rectangular range queries. The range, segment, and interval trees. Kd-trees.
  • Dynamization of data structures.
  • Applications to problems involving iso-oriented rectangles.
  • Higher-dimensional rectangular queries and intersection detection.
  • Half plane range queries and the ham sandwich theorem.
  • Generalizations to higher dimensions and more complex queries.