Computational Geometry - 236719
Dr. Gill Barequet
Spring 2001

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

(9.7.01) A 2nd-chance quiz will take place on Sunday 22/7 9am at T-8.

(25.6.01) Project information (summary of an e-mail message): (a) Let me know your final singleton/pair decisions. (b) Submission date: 15/7/01. Approach me for extensions. (c) Software invocation: Singletons: % str-skl in-file.dat out-file.m ; Pairs: % interpol in-file-1.dat in-file-2.dat out-file.m . (d) Software structure: Separate algorithmics from i/o.

(11.6.01) Data files for the project are now available (follow this link). Start with reading the file files/_file_formats.

(29.5.01) Ex3 is now available through this web page.

(16.5.01) Ex2 is now available through this web page.

(8.5.01) Disregard the previous note. There will be a lecture on Thursday 17/5.

(6.5.01) The lecture of Thursday 17/5 is canceled.

(16.4.01) Please start to team up in singletons or pairs for the project. We will start dealing with it next week.

(15.4.01) Those who have not registered yet to the course mailing list are requested to do that before the due date of ex1.

(4.4.01) There will be no lectures on Thursday 19/4 (Holocaust day, no studies 12:30-2:30) and Thursday 26/4 (Independence day). I will be away on Thursday 3/5 (Miluim) and Thursday 7/6 (trip). Maybe my TA will give one of these lectures; details will follow. Two compensation lectures will be given on Sunday 22/4 and on Sunday 6/5, both at 4:30pm in Taub 4.

(3.4.01) ex1 is posted in the course web page.

(14.3.01) The lecture of Thursday 22/3/01 is canceled. A compensation lecture will be given on Sunday 15/4/01 16:30 in Taub 4.

(14.3.01) Note the set up grading policy.

(28.2.01) The easiest way to get into the course e-mail list is by requesting this from me by E-mail. Please also mention your id #, faculty, and toward which degree you are studying.

Bibliography

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

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

Grading Policy

Assignments: 30% (submission in singletons!!);
Midterm exam (Takef): 30-35% (Sunday 10/6/01 16:30 in T-9);
Project: 35-40% (programming assignment, course recognized as a project).

Assignment 1: given 5/4/01, due 19/4/01.

Assignment 2: given 17/5/01, due 31/5/01.

Assignment 3: given 31/5/01, due 21/6/01.

Course summary

(1) 8.3.01 Introduction

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

(2) 15.3.01 Plane sweep, DCEL

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

(3) 29.3.01 DCEL, Polygon triangulation (I)

Application of DCEL to a map-overlay algorithm. Its use for polygon union, intersection, and difference. The art-gallery theorem. Triangulating a monotone polygon.

(4) 5.4.01 Polygon triangulation (II), Linear programming (I)

Partitioning a simple polygon into monotone pieces. What is linear programming. A D&C algorithm for half-planes intersection.

(5) 15.4.01 Linear programming (II)

An incremental algorithm for half-planes intersection. Randomized linear programming. Unbounded linear programming. Smallest enclosing disk of a 2D point set.

(6) 22.4.01 Orthogonal range searching

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

(7) 6.5.01 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.)

(8) 10.5.01 Voronoi diagram

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

(9) 17.5.01 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.

(10) 24.5.01 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.

(11) 31.5.01 The crossing-number lemma

The crossing-number lemma and applications. (Project description.)

(12) 14.6.01 Miscellaneous

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

(13) 21.6.01 Putting things together

Some 2-point site distance functions and their Voronoi diagrams. Two open problems.