Computational Geometry
G22.3033009
Prof. Micha Sharir
Fall 2000, Wed 79 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 fourfive) 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
 Simpleminded algorithms: Gift wrapping
 Graham's Walk; analysis
 DivideandConquer approaches
 Average case behavior
 Applications of convex hulls: width; diameter; normal diagram
 Convex hulls in higher dimensions
 Convex polyhedra, Euler's formula, polyhedra in 3D
 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 halfplanes; dual formulation as a convex hull
problem
 Intersection of n halfspaces; 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; postoffice problem;
Euclidean minimum spanning trees; triangulation;
motion planning for a disc
 Fortune's linesweeping algorithm
 Extensions: Nonpoint sites, knearest neighbor diagrams;
diagrams in higher dimensions
(7) Range Queries and Multidimensional Data Structures:
 Twodimensional rectangular range queries. The range, segment, and
interval trees. Kdtrees.
 Dynamization of data structures.
 Applications to problems involving isooriented rectangles.
 Higherdimensional rectangular queries and intersection detection.
 Half plane range queries and the ham sandwich theorem.
 Generalizations to higher dimensions and more complex queries.
