Personal tools
You are here: Home Courses Applied Computational Geometry Spring 2009
« September 2021 »
Log in

Forgot your password?



a.k.a. Applied Geometric Computing (0368-4073)

Instructor: Dan Halperin

Lecture: Monday 1600-1900, Schreiber 008

Office hours: Monday 1900-2000, Schreiber 219

Help desk: Efi  Fogel,  Eric Berberich: Monday 1500-1600 @ ACG lab (Schreiber basement)

TA: Guy Zucker contact



Transforming geometric algorithms into effective computer programs is a difficult task. The last decade has seen significant progress in this area, some of which we will review in the course. We will discuss various issues in computational geometry, algorithmic and numerical, from a practical perspective, as well as applications of geometric algorithms in several domains.

The course will concentrate on the following topics:
 Arrangements of curves and surfaces and their applications
 Minkowski sums
 Geometric rounding
 Movable separability of sets and assembly planning

Other topics that will be covered, as time permits, include:
 Delaunay triangulations and their relatives as modeling tools
 The CGAL project and library (beyond arrangements and Minkowski sums)
 Motion planning techniques in algorithmic robotics
 Dynamic maintenance of large kinematic chains

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.


Computational Geometry. Knowledge of C++ or willingness to learn the language


The final grade will be determined by a short multiple-choice exam, and mostly by homework assignments including one large-scale project. It is possible to work and submit the assignments in pairs.

The exam will be held on Tuesday, 30/6/09, between 9:00 and 11:00. For more information about the exam click here.




  • Assignment 1, due March 23rd  [pdf] [examples]
  • Assignment 2, due April 6th [pdf] [examples NEW! example0] [ NEW! Detailed tutorial for CGAL installation on windows ]
    CGAL version 3.4, 64 bit, (without QT4 support) is installed at /usr/local/lib/cgal_3.4-1_qt3. If you want to use it, set the environment variable CGAL_DIR:
         setenv CGAL_DIR /usr/local/lib/cgal_3.4-1_qt3/lib/CGAL
    and proceed as usual.
  • Assignment 3, due May 15th [pdf]  [hints for Ex. 3.3] [New! I/O instructions and examples]
  • Assignment 4, due June 11th [pdf] [additional information]
    • The pdf was updated on 21/05/09. The word "vertex" was replaced by the word "edge" in the line before the last.
    • The data-set archive data.tar.gz was updated on 26/05/09 with additional data files.
    • The Gaussian-map section was updated on 02/06/09 with instructions for obtaining the point geometric embedding of a primal vertex that corresponds to a Gaussian-map face.
    • The Gaussian-map section was updated (yet again) on 03/06/09 with
      • additional instructions to compile code that constructs Minkowski sums based on the Gaussian-map method, and
      • instructions to eliminate coplanar facets of a polytope.
    • A patch for merge_coplanar_planes.hpp was added in 07/06/09. The patch enables computing the width of dodecahedron.wrl and iso_cube.wrl.

Course Summary

  • 2/3/09 Intorduction [pdf file; up till slide 38], to be continued
  • 9/3/09 Introduction, continued (2 hour lesson, Purim)
  • 16/3/09 Gentle Introduction to CGAL [pdf
  • 23/3/09 2D Arrangements [pdf]
  • 30/3/09 3D Arrangements [pdf] (we covered slides 1-23 in class)
  • 20/4/09 3D Arrangements, continued (up till slide 30); 
        Minkowski Sums, Preliminaries [pdf] 2D Minkowski sums, general polygonal
  • 27/4/09 3D Minkowski Sums of Convex Polyhedra (2 hour lesson)[pdf]
    • Minkowski sum construction via convex hull [cpp]
    • Minkowski sum construction via Gaussian map [cpp]
  • 4/5/09 3D Arrangements, completed (from slide 31); 
        Spherical arrangements and more (up till slide 7) [pdf]
  • 11/5/09 Minkowski sums, the general polygonal case (slides 1-19) [pdf]
  • 18/5/09 Minkowski sums, the general polygonal case (slides 20-end);

        more on arrangements of atom spheres: depth order, vertical decomposition

  • 25/5/09 Geometric rounding (up till slide 44) [pdf]
  • 1/6/09 Geometric rounding, completed
  • 8/6/09 2D Voronoi diagrams via envelopes of surfaces in space [pdf]
  • 15/6/09 Movable separability and assembly planning [pdf]
Document Actions