Computational Geometry (Comp 163)
Fall 2009-10
Halligan 108, E+ (MW 10:30-11:45)

Syllabus

Fundamental techniques, data structures, and algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, the Voronoi diagram and Delaunay triangulation of a point set, polygon triangulation, range search, linear programming, and point location. Some topics of discrete geometry, e.g., the crossing number of a graph and its applications, are also covered.

Prerequisite: Algorithms (Comp 160) or consent.

News and Messages

(Oct/23/09) Please fill out the Online Computer Science Midterm Course Feedback. This link will be kept alive until Monday October 26, 2009.

(Oct/20/09) By majority vote, the mid-term quiz will be held during the class of 11/2. It will cover all the material taught until and including the lecture of Monday 10/19, that is, Point Location.

(Oct/14/09) Details about the Fall Workshop on Computational Geometry (11-13-14) and the following tutorial day (11/15) full of interesting lectures on various topics in Discrete and Computational Geometry can be found here. Hurry up and register!

(Oct/6/09) Ex2 was posted in the web page.

(Sep/21/09) Ex1 was posted in the web page.

(Sep/16/09) A kind reminder: Please register to the mailing-list of the course by sending me an e-mail message with your full name and e-mail address.

(Aug/27/09) I will be away during the first week of the semester, so I will miss the first class of Wednesday, September 9, 2009. Dr. Souvaine will replace me and give the first introductory lecture.

(Aug/26/09) PDF versions of all my PPT presentations will be posted in this web page. Please devote 15 minutes before class to browsing through the next presentation I am going to teach. You are not expected to study the material in it, just to know which subject I am going to talk about.

(Aug/25/09) I will post here messages on a regular basis. In addition, I will maintain a mailing-list of the course, to which each student is asked to register by simply sending me an e-mail message with his or her full name and e-mail address. (You may also specify your major subject, so that I'll know you better.) Note: this registration has nothing to do with the formal enrollment to the course!

Bibliography

	Main text book: Computational Geometry: Algorithms and Applications (3rd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2008.
	For background: Computational Geometry in C (2nd ed.), J. O'Rourke, Cambridge University Press, 2000.

Grading Policy

Home assignments: ~15% (submission in singletons!! guidelines for submitting homework solutions: ps, pdf);
Midterm quiz: ~20% (noncompulsory, Monday Nov/02/2009, 10:30-12:00, H108);
Final exam: ~65% (Wednesday Dec/16/2009, 15:30-17:30, H108).

Assignment 1: given 09/21/2009, due 10/14/2009.

Assignment 2: given 10/06/2009, due 11/06/2009.

Assignment 3: given 11/05/2009, due 11/27/2009.

Staff

Instructor: Gill Barequet (barequet@cs.tufts.edu), Halligan E011, x72247, office hours: any time by appointment.
TA: Mashhood Ishaque (mishaq01@cs.tufts.edu), Halligan extension, office hours: by appointment.

Summary and Slides

(1) Introduction

What is Computational Geometry? Example problems and motivations. Naive, incremental, and divide-and-conquer convex-hull algorithms.

(2) Vectors, Plane sweep

Vector cross product and orientation test. Segment-intersection test. Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.

(a) Planar graphs

Graph definition, planar graphs, Euler's formula, the DCEL structure.
(Graph material is found in the 2nd lecture file; DCEL stuff does not have notes.)

(3) Polygon triangulation

The art-gallery theorem. Partitioning a simple polygon into monotone pieces. Triangulating a monotone polygon.

(4) Linear programming

What is linear programming. A D&C algorithm for half-planes intersection. An incremental algorithm for half-planes intersection. Randomized linear programming. Unbounded linear programming. Smallest enclosing disk of a 2D point set.

(b) Polygonal skeletons (will NOT be taught this semester)

Straight skeleton of a polygon and a polyhedron. Their complexities, and algorithms to compute them.

(5) Orthogonal range searching

1D range searching. 2D kd-trees. 2D Range trees.

(6) Point location

Slabs structure. Trapezoidal map. A randomized incremental algorithm for computing a trapezoidal map. Worst- and average-case Time/Space analysis of the algorithm. Handling degeneracies.

(7) Voronoi diagram

Definition and variants. A plane-sweep algorithm for computing the Voronoi diagram of a point set.

(c) Other Voronoi diagrams (self reading)

More and alternative definitions. Lloyd's algorithm.

(8) Duality

A point-line duality in the plane and its properties.

(9) Line Arrangements

Line arrangements and their properties. The zone theorem. Computing an arrangement of lines. Levels in line arrangements. Halfspace discrepancy and its dual problem.

(d) Space Partitioning (will NOT be taught this semester)

BSP tress, quadtress.

(10) Delaunay triangulation

Triangulation of a point set. Angle vector and the triangulation that maximizes it. Delaunay triangulation and its relation to the angle vector. A randomized incremental algorithm for computing the Delaunay triangulation.

(11) The crossing-number lemma

The crossing-number lemma and a few of its applications.

(12) 2-point site Voronoi diagrams

Some 2-point site distance functions and their respective Voronoi diagrams.

(13) A few theorems

The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes.

Lecture Notes

Stefan Schirra, MPI, summer 2002
Dave Mount, Univ. of Maryland, fall 2002
Diane Souvaine, Tufts, spring 2004
Micha Sharir, Tel Aviv University, fall 2008