APPLIED aspects of COMPUTATIONAL GEOMETRY
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
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
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.
PLEASE READ THE NEW SUBMISSION GUIDELINES [pdf]
- 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
- 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.
- 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);
- 27/4/09 3D Minkowski Sums of Convex Polyhedra (2 hour lesson)[pdf]
- 4/5/09 3D Arrangements, completed (from slide 31);
- 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