Computational Geometry
Spring 99
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 lowdimensional space.
News and Messages
The 29/6 class is canceled; it will be given in 27/6 instead in F413.
Ex3 will be given in 15/6. The due date (strict this time) is 29.6.
The due date of ex2 was 8/6. I will not accept submissions later than 15.6.
The exam stays on 13/7/99. Hour will be published later.
[CANCELED]
Please notify me by Email ASAP if you want/don't want to move
the exam from 13/7/99 to 29/6/99.
The exam date was set to Tuesday 13.7.99.
The due date of ex1 is 27/4. I will not accept submissions later than 6.5.
All students who are not on my mailing list should send me an Email note.
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: 3040%; Final exam: 6070%.
Assignment 1: given 13/4/99, due 27/4/99.
Assignment 2: given 25/5/99, due 8/6/99.
Assignment 3: given 15/6/99, due 29/6/99.
Course summary

23.3.99
Introduction

What is Computational Geometry? Example problems and motivations.
Naive, incremental, and divideandconquer convexhull algorithms.

29.3.99
Plane sweep

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

13.4.99
DCEL (short talk)

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

27.4.99
Polygon triangulation

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

4.5.99
Linear programming, I

What is linear programming. Algorithms for halfplanes intersection:
1. Divide and conquer; 2. Incremental.

11.5.99
Linear programming, II

Randomized linear programming. Unbounded linear programming.
Smallest enclosing disk of a 2D point set.

18.5.99
Orthogonal range searching

1D range searching. kdtrees. Range trees.

25.5.99
Point location, I

Slabs structure. Trapezoidal map. A randomized incremental algorithm for
computing a trapezoidal map. Time/Space analysis of the algorithm.

1.6.99
Point location, II; Voronoi diagram,

Handling degeneracies in point location.
A planesweep algorithm for computing the Voronoi diagram of a point set.

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

15.6.99
Delaunay triangulation, I

Triangulation of a point set. Angle vector and the triangulation that
maximizes it. Delaunay triangulation and its relation to the angle vector.

22.6.99
Delaunay triangulation, II; Miscellaneous

A randomized incremental algorithm for computing the Delaunay triangulation.
The upperbound theorem. Interpretations of Voronoi diagrams. Zone theorems.
Envelopes of lines and planes. The crossingnumber lemma.

27.6.99
Putting things together

Using various techniques for proving the combinatorial complexities of
several 2point site Voronoi diagrams.