Applied Computational Geometry, Spring 2009

0368-4073, a.k.a. Applied Geometric Computing

Lecture: Monday 16:00–19:00, Schreiber 008

Instructor: Dan Halperin
Office hours: Monday 19:00–20:00, Schreiber 219

Help desk: Efi Fogel,  Eric Berberich: Monday 15:00–16:00 @ ACG lab (Schreiber basement)
Teaching assistant: Guy Zucker

Syllabus

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.

Prerequisites

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

Grade

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.

Links

• CGAL homepage
• Tutorial—CGAL installation on windows
• snap rounding applet

Assignments

PLEASE READ THE NEW SUBMISSION GUIDELINES [pdf]

• Assignment 1, due March 23rd  [pdf]
• Assignment 2, due April 6th [pdf] [ 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]
• Assignment 4, due June 11th [pdf]
  • 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 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.