Computational Geometry

Spring 2001

Final Assignment

Oral exam schedule

Instructor: Dan Halperin

Monday, 16:00--19:00
Schreiber 008

Office hours: Wednesday, 16:00--17:00
Schreiber 219

The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.


The main textbook of the course is
Computational Geometry: Algorithms and Applications (CGAA)
by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.

A bibliographic list for the course.

Search in the computational geometry bibliography

Assignments, Examination, and Grades:

The final grade will be determined by: 70% - homework assignments including one large-scale assignment, and 30% - oral exam.

Assignment no. 1 (ps file), due: April 2nd, 2001.

Assignment no. 2 (ps file), due: April 30th, 2001.

Assignment no. 3 (ps file), due: May 21st, 2001.

Assignment no. 4 (ps file), due: June 11th, 2001.

Final Assignment

Final Assignment, Theory (ps file), due: July 10th, 2001.

Final Assignment, Implementation (ps file), due: July 15th, 2001.
Example program: computing the Delaunay triangulation of a set of points and transforming it into planar-map representation.

Course Summary:

Below you'll find a very brief summary of what was covered in class during the semester. This should not be taken as a complete description of the course's contents.

For an outline of the course, see the course summary in the 1998 computational geometry course .

5.3.01 Introduction

What is Computational Geometry? Course outline, motivation and techniques. Naive convex hull algorithms (see Chapter 3 in O'Rourke's book). Side-of-line test.

12.3.01 Convex hull computation continued; Line segment intersection

Graham's O(n log n) algorithm (Chapter 1 in CGAA). The orientation test. Lower bound for convex hull algorithms.

Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann's plane sweep (Chapter 2 in CGAA). A survey of more efficient algorithms for the problem.

The last segment in CG Video Review 1992, by Tal, Chazelle, and Dobkin. Based on the paper: An optimal algorithm for intersecting line segments in the plane, by Chazelle and Edelsbrunner, J. of the ACM, Vol. 39, 1992, pp. 1--54. For recent advances on this problem see "Notes and comments" at the end of Chapter 2 of CGAA.

26.3.01 Doubly-connected-edge-list; Map overlay

The doubly connected edge list; overlay of planar subdivisions (CGAA, Chapter 2).

2.4.01 Polygon triangulation; Art gallery problems

We have shown that $\lfloor n/3 \rfloor$ guards are sometimes necessary and always sufficient to guard a simple polygon with n vertices. We have shown that every simple polygon can be triangulated; that the triangulation graph is 3-colorable; that the dual of the triangulation graph is a tree.

A naive algorithm that mimics the triangulation existence proof can triangulate a simple polygon with n vertices in O(n^2) time. A more efficient algorithm does it in O(n\log n) by first decomposing a polygon into monotone polygons and then triangulating each of the resulting monotone subpolygons.

The material covered in class could be found in O'Rourke's book, Chapters 1 and 2, and in CGAA, Chapter 3. (The description of how to decompose a polygon into y-monotone polygons follows O'Rourke's presentation.)

Video segment no.~1 in CG Video Review 1994, An O(n\log n) implementation of the Douglas-Peucker algorithm for line simplification, by Hershberger and Snoeyink. For details see Proc. of the 10th ACM Symposium On Computational geometry, pp. 383--384.

5.4.01 Tetrahedralization; Intersection of halfplanes; Casting; LINEAR PROGRAMMING

We reviewed the results for triangulation shown in the previous lesson. Next, a few facts about tetrahedralization where surveyed: not every polyhedron is tetrahedralizable with vertices of the polyhedron only (see also Assignment no. 2); the algorithm by Chazelle and Palios (see next paragraph for more details); in general putting guards at the vertices of a polyhedron is insufficient for guarding the polyhedron; there are polyhedra with $n$ vertices that require $\Omega(n^{3/2}))$ guards.

We have shown an $O(n\log n)$ algorithm for computing the intersection of $n$ halfplanes. This question was motivated by a problem in casting: computing whether a given polyhedron is castable. See Chapter~4 in CGAA.

We presented the linear programming problem, then a randomized incremental algorithm for LP in 2D, running in expected linear time, and finally "backward analysis" for randomized algorithms. See Chapter 4 of CGAA.

16.4.01 Linear programming, cont'd

The unbounded case; extension to higher dimensions; Megiddo's deterministic linear time algorithm (see Preparata and Shamos, Section 7.2.5)

23.4.01 Minimum enclosing disc; Orthogonal Range serach

Randomized linear time algorithm for finding the minimum enclosing disc of a set of points in the plane. CGAA, Chapter 4.

Two structures for orthogonal range search were described and analyzed: kd-trees and range trees in any fixed dimension. CGAA, Chapter 5.

30.4.01 Orthogonal Range serach: handling degeneracies; Fractional cascading; Point location

Randomized incremental construction of trapezoidal maps, and point location search structure. CGAA, Chapter 6. We described the structure; the performance analysis will be given next week.

A video segment from CG Video Review 1992 by Palios and Phillips: Computing a tetrahedralization of a simple polyhedron. The segment illustrates the algorithm by Chazelle and Palios, described in their paper "Triangulating a nonconvex polytope", Discrete and Computational Geometry, Vol. 5, pp. 505--526, 1990.

A video segment by Murphy and Skiena (ACM CG Video review 1993) describing their software "Ranger" was shown (nearest neighbor and orthogonal range search in high-dimensional space).

7.5.01 Point location cont'd; Voronoi diagrams

Analysis of the randomized incremental construction of trapezoidal maps, and point location search structure. CGAA, Chapter 6. Tail estimate. Relaxing the general position assumption.

Voronoi diagrams---introduction: combinatorial complexity and some properties.

14.5.01 Voronoi diagrams

A sweep algorithm to compute the Voronoi diagram of n points in the plane in time O(n \log n)---Fortune's algorithm. CGAA, Chapter 7.

Additional references: (1) F. Aurenhammer, Voronoi diagrams: A survey of a fundamental geometric data structure , ACM Comput. Surv. 23 (1991), pp. 345--405. (2) A book full of applications---A. Okabe, B. Boots and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams , John Wiley & Sons, 1992.

21.5.01 Arrangements of lines; Duality

Point-line duality. Incremental construction of arrangements of lines. Computing the halfplane discrepancy of a set of points in a square. CGAA, Chapter 8.

The Lifting Transform and its application to the in-circle test

11.6.01 Delaunay triangulation

Triangulating a set of points in the plane. Legal tringulations; edge flip. Delaunay triangulations. CGAA, Chapter 9.

18.6.01 Windowing; segment intersection structures

Windowing. Orthogonal range search on segments in the plane. Interval trees. Segment trees. CGAA, Chapter 10.

Video segments: (i) "Visualizing Fortune's sweepline algorithm" by Seth Teller and (ii) "Moving a disc between polygons" by Stefan Schirra (bothe from the ACM CG Video Review 1993), and (iii) "The convex hull of ellipsoids" by Geismann, Hemmer and Schoemer (ACM CG Video Review 2001).

Last update: June 19th, 2001