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 low-dimensional space.

News and Messages

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 E-mail 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 E-mail 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: 30-40%; Final exam: 60-70%.

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 divide-and-conquer convex-hull algorithms.

29.3.99 Plane sweep

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

13.4.99 DCEL (short talk)

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

27.4.99 Polygon triangulation

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

4.5.99 Linear programming, I

What is linear programming. Algorithms for half-planes 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. kd-trees. 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 plane-sweep 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 upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes. The crossing-number lemma.

27.6.99 Putting things together

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