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,
and point location.
Some topics of discrete geometry, e.g., the crossing number of a graph and
its applications, are also covered.
News and Messages
(30/dec/15)
Ex3 was posted below.
(25/dec/15)
Ex4 was posted below.
(23/dec/15)
Ex2 was posted below.
(9/Nov/15)
Ex1 was posted below.
(7/Nov/15)
There will be no recitation (tutorial) on Tuesday, November 10, 2015.
(3/Nov/15)
The lecture of today is canceled.
(21/Oct/15)
Slides of all lectures and recitations are available below.
(21/Oct/15)
All students (including free listeners) are kindly requested to join
the mailing list of the course.
(This is in addition to the formal registration to the course!
One can leave this mailing list at any time.)
For joining the mailing list, please e-mail me (barequet@cs) your
full name, id #, faculty, and degree toward which you study.
Bibliography
Grading Policy
3 Home assignments (dry): ~12.5% (Takef, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Wednesday 27/Jan/16, time TBA, location TBA;
2nd term: Friday 11/Mar/16, hopefully no need to!)
Assignment 1 (dry): given 10/Nov/15, due 24/Nov/15.
Assignment 2 (dry): given 23/Dec/15, due 06/Jan/16.
Assignment 3 (dry): given 31/Dec/15, due 14/Jan/16.
Assignment 4 (wet): given 25/Dec/15, due 21/Jan/16
(Graphics files,
sample input files,
paper,
FAQ file)
Course summary and slides
-
(1) Introduction
-
What is Computational Geometry? Example problems and motivations.
Naive, incremental, and divide-and-conquer convex-hull algorithms.
-
(2) Vectors, Plane sweep
-
Vector cross product and orientation test. Segment-intersection test.
Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.
-
(a) Planar graphs
-
Graph definition, planar graphs, Euler's formula, the DCEL structure.
-
(3) Polygon triangulation
-
The art-gallery theorem.
Partitioning a simple polygon into monotone pieces.
Triangulating a monotone polygon.
-
(4) Linear programming
-
What is linear programming. A D&C algorithm for half-planes intersection.
An incremental algorithm for half-planes intersection.
Randomized linear programming. Unbounded linear programming.
Smallest enclosing disk of a 2D point set.
-
(b) Polygonal skeletons
-
Straight skeleton of a polygon and a polyhedron. Their complexities, and
algorithms to compute them.
-
(5) Orthogonal range searching
-
1D range searching. 2D kd-trees. 2D Range trees.
-
(c) Fractional cascading
-
Fractional cascading for range searching.
-
(6) 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.
-
(7) Voronoi diagram
-
Definition and variants.
A plane-sweep algorithm for computing the Voronoi diagram of a point set.
-
(d) Voronoi diagram
-
More and alternative definitions. Lloyd's algorithm.
-
(8) Duality
-
A point-line duality in the plane and its properties.
-
(9) Line Arrangements
-
Line arrangements and their properties. The zone theorem.
Computing an arrangement of lines. Levels in line arrangements.
Halfspace discrepancy and its dual problem.
-
(e) Space Partitioning
-
BSP trees, quadtress.
-
(10) 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) The crossing-number lemma
-
The crossing-number lemma and a few applications of it.
-
(12) 2-point site Voronoi diagrams
-
Some 2-point site distance functions and their respective Voronoi diagrams.
-
(13) A few theorems
-
The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems.
Envelopes of lines and planes.