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
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.
Computational Geometry: Algorithms and Applications,
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry in C,
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.
What is Computational Geometry? Example problems and motivations.
Naive, incremental, and divide-and-conquer convex-hull algorithms.
Vector cross product and orientation test. Segment-intersection test.
Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.
DCEL (short talk)
The DCEL data structure. Application to a map-overlay algorithm.
Its use for polygon union, intersection, and difference.
The art-gallery theorem. Partitioning a simple polygon into monotone pieces.
Triangulating a monotone polygon.
Linear programming, I
What is linear programming. Algorithms for half-planes intersection:
1. Divide and conquer; 2. Incremental.
Linear programming, II
Randomized linear programming. Unbounded linear programming.
Smallest enclosing disk of a 2D point set.
Orthogonal range searching
1D range searching. 2D kd-trees. 2D Range trees.
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.
Definition and variants.
A plane-sweep algorithm for computing the Voronoi diagram of a point set.
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.
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.
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.