Computational Geometry
Spring 2000


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, point location, in spaces of any dimension. Some topics of Discrete Geometry are also covered (e.g., the crossing number of a graph).

News and Messages

Minutes from the last class, on the crossing-number lemma, are available here.

On 26/6 there is no CG class.

Please download ex3 from this web page.

Please download ex2 from this web page.

The lecture on 8/5/00 (Memorial Day Eve) is canceled. Note also that there will be no lectures on 15/5 and 29/5, in which teaching will be as in Thursday and Tuesday, respectively.

The lecture on 13/3/00 is canceled. A compensation lecture will be given on Thursday 23/3/00 16:30 in Taub 8.

Every student in the course is requested to enter the course E-mail list. To this aim please send me a message with your E-mail address, name, id number, faculty, and sought degree.


Computational Geometry: Algorithms and Applications, M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 1997.

Computational Geometry in C, J. O'Rourke, Cambridge University Press.

Assignments and Grades

Assignments: 30% (submission in singletons!!); Final exam: 60-70%.

Assignment 1: given 10/4/00, due 1/5/00.

Assignment 2: given 22/5/00, due 5/6/00.

Assignment 3: given 12/6/00, due 26/6/00.

Course summary

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

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

23.3.00 DCEL (short talk)
The DCEL data structure. Application to a map-overlay algorithm. Its use for polygon union, intersection, and difference.

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

3.4.00 Linear programming, I
What is linear programming. Algorithms for half-planes intersection: 1. Divide and conquer; 2. Incremental.

10.4.00 Linear programming, II
Randomized linear programming. Unbounded linear programming. Smallest enclosing disk of a 2D point set.

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

1.5.00 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.

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

5.6.00 Duality; Arrangements of lines
A definition of duality in the plane. Halfspace discrepancy and its dual problem. Computing an arrangement of lines. Levels in line arrangements.

12.6.00 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.

19.6.00 Miscellaneous
The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes. The crossing-number lemma and applications. Some 2-point site distance functions and their respective Voronoi diagrams.