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.

### Course Summary

- 02/03/09 Introduction [pdf file; up till slide 38], to be continued
- 09/03/09 Introduction, continued (2 hour lesson, Purim)
- 16/03/09 Gentle Introduction to CGAL [pdf]

- 23/03/09 2D Arrangements [pdf]
- 30/03/09 3D Arrangements [pdf] (we covered slides 1-23 in class)
- 20/04/09 3D Arrangements, continued (up till slide 30);

Minkowski Sums, Preliminaries [pdf] 2D Minkowski sums, general polygonal

- 27/04/09 3D Minkowski Sums of Convex Polyhedra (2 hour lesson)[pdf]
- Minkowski sum construction via convex hull [cpp]

- 04/05/09 3D Arrangements, completed (from slide 31);

Spherical arrangements and more (up till slide 7) [pdf]

- 11/05/09 Minkowski sums, the general polygonal case (slides 1-19) [pdf]
- 18/05/09 Minkowski sums, the general polygonal case (slides 20-end);

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