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

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