Personal tools
You are here: Home Courses Computational Geometry Spring 2014 Computational Geometry - Spring 2014
« March 2017 »
Log in

Forgot your password?

Computational Geometry - Spring 2014

Instructor: Dan Halperin , danha AT post

Grader: Israela Slomon, israela5 AT
    mailbox #263, Schreiber, 2nd floor

Monday, 16:00--19:00
room: Schreiber 008

Office hours: Monday, 19:00--20:00

A makeup lesson will be held on Friday, May 2nd, 2014, 10:00 to 12:30, in Schreiber 008,  instead of the lesson on the last week of the semester.

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. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.


The main textbook of the course is:

Computational Geometry: Algorithms and Applications (CGAA), 2nd or 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.

A bibliographic list for the course

Assignments, Examination and Grade:

The standard assignments will account for 10% of the final grade, in case they improve the final grade. 
The grade in the final exam, to be held on Wednesday 18th, 2014, will account for the remaining 90% 
of the grade in the course. Although the assignment grades will be used only for improving the final grade, 
submission of the assignments is mandatory and a prerequisite for taking the exam.

Exam(ple), pdf file

About halfway through the course, we will present a programming assignment.
We encourage you to submit the programming assignment as well. This is not mandatory.
If however you do submit it, then your grade breakdown will be 10% the standard assignments, 
20% the programming assignment, and 70% the final exam. Here as well, the assignments grades will
be counted toward the final grade only if they improve it.
NOTICE: The weight of the programming assignment is 20% as described in class (previously a different number was 
incorrectly mentioned here).

Assignment no. 1 (pdf file), due: March 10th, 2014.

Assignment no. 2 (pdf file), due: April, 7th, 2014.

Assignment no. 3 (pdf file), due: April, 28th, 2014.

Programming Assignment (pdf file), due: May 12th, 2014 (you may work and submit in pairs). Additional information.

Assignment no. 4 (pdf file), due: May, 26th, 2014.

Course Summary:

Below you'll find a very brief summary of what was covered in class during the semester.
This should not be taken as a complete description of the course's contents.
For an outline of the course, see for example, the course summary in the 2010 computational geometry course.

What is Computational Geometry? Course outline, motivation and techniques. Naive convex hull algorithms (see Chapter 3 in O'Rourke's book). Orientation (Side-of-line) test. Gift wrapping. Graham's O(n log n) algorithm (Chapter 1 in CGAA). Lower bound for convex hull algorithms.
Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann's plane sweep. The doubly-connected edge list (DCEL), and overlay of planar subdivisions (CGAA, Chapter 2).
Polygon terms and definitions. The art gallery. Regularization and triangulation. [slides] [handouts]
A problem in casting. Computing the intersection of halfplanes; computing lower and upper envelopes of curves. Linear Programming in 2D, the bounded case (CGAA, Chapter 4).
Linear Programming continued. The unbounded case in 2D; sketch of LP in 3D. The minimum enclosing disk problem (CGAA, Chapter 4).
Orthogonal range searching, the 2D case (CGAA, Chapter 5).
Orthogonal range searching, the dD case (CGAA, Chapter 5). Trapezoidal maps and planar point location (CGAA, Chapter 6).
Introduction to CGAL [slides] [handouts]. CGAL 2D Arrangements package [slides] [handouts].

Voronoi diagrams of points in the plane: structure, complexity, and Fortune's algorithm (CGAA, Chapter 7). 

Bird's eye view: Voronoi diagrams of segments and their use for high-clearance motion planning.

2.5.14 (Friday)

Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8). 

          The minimum area triangle problem (CGAL Arrangements and Their Applications, Section 4.2.1). 

Delaunay triangulations (CGAA, Chapter 9, up till and including Section 9.2).


Optimal randomized incremental construction for guaranteed logarithmic planar point location; talk by Michal Kleinbort  [slides].
        Related work:
             Helmut Alt, Ludmila Scharf: Computing the depth of an arrangement of axis-aligned rectangles
             Thomas Ottmann, Peter Widmayer: On translating a set of line segments   (how to efficiently compute the total order)
The role of computational geometry in GIS problems; talk by Eli Packer  [slides].


Connections among point configurations, hyperplane arrangements, lower and upper envelopes, Delaunay triangulations and Voronoi diagrams. The material does not appear in full in one place. Some of it can be found in CGAA, Sections 11.4 and 11.5.                    

A bird's eye view of a randomized incremental construction of the convex hull of points in three-space (CGAA, Chapter 11)

Computing the half-plane discrepancy of point sets in a square and levels in arrangements of lines (CGAA Sections 8.1 and 8.4).  


Multi-robot motion planning; talk by Kiril Solovey [slides].
        Unlabeled motion planning paper [link]




Document Actions