Computational Geometry
Spring 2000
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,
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 crossingnumber 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 Email list.
To this aim please send me a message with your Email address, name, id
number, faculty, and sought degree.
Bibliography
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: 6070%.
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 divideandconquer convexhull algorithms.

20.3.00
Plane sweep

Vector cross product and orientation test. Segmentintersection test.
Convexpolygon queries. Planesweep paradigm. Segmentintersection algorithm.

23.3.00
DCEL (short talk)

The DCEL data structure. Application to a mapoverlay algorithm.
Its use for polygon union, intersection, and difference.

27.3.00
Polygon triangulation

The artgallery theorem. Partitioning a simple polygon into monotone pieces.
Triangulating a monotone polygon.

3.4.00
Linear programming, I

What is linear programming. Algorithms for halfplanes 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 kdtrees. 2D Range trees.

1.5.00
Point location

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

22.5.00
Voronoi diagram

Definition and variants.
A planesweep 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 upperbound theorem. Interpretations of Voronoi diagrams. Zone theorems.
Envelopes of lines and planes. The crossingnumber lemma and applications.
Some 2point site distance functions and their respective Voronoi diagrams.