Applied Geometric Computing and CGAL
Spring 2005

Instructor: Dan Halperin
Wednesday 16-19, Schreiber 7
Office hours: Wednesday 19-20, Schreiber 219

Teaching assistant (assignments): Idit Haran
Meeting by appointment

Helpdesk and forum : Baruch Zuckerman (baruchzu@post)
Wednesday 14-16, the robotics lab (Schreiber basement)

[Minkowski Sums]

The final project, due August 10th, 2005


More information for the assignments (by the TA)

Assignment no. 1 (pdf file), due: March 30th, 2005.

Assignment no. 2 (pdf file), new due date: May 11th, 2005.

More information on Exercise 2.3 (pdf file).

Assignment no. 3 (pdf file), due: June 1st, 2005.

Preparing for class

for the class on 20/4: Snap rounding

for the class on 4/5: Software design, short bibliography

Transforming geometric algorithms into effective computer programs is a difficult task. The last decade has seen tremendous progress in this area, some of which we will review in the course. The topics that will be covered include:
 why is it difficult to implement geometric algorithms
 the exact geometric-computing paradigm
 exact number types: filtered rationals, extended float, algebraic numbers
 the CGAL project and library
 generic programming techniques applied to computational geometry
 the CGAL arrangement package
 related libraries: LEDA, BGL, CORE, GMP
 geometric rounding
 controlled perturbation
 exact and hybrid motion-planning algorithms
 geometric modelling of molecules

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.

The final grade will be determined by homework assignments including one large-scale assignment, and the presentation of the latter. It is possible to work and submit the assignments in pairs.

Useful links

CGAL's global site, CGAL @ TAU
Robust geometric computing at TAU
The Boost Graph Library (BGL)

Course summary

23.2.2005 Introduction

2.3.2005 Arrangements - overview

9.3.2005 Introduction to generic programming and CGAL, Efi Fogel

Additional sources:
Two computational geometry libraries by Lutz Kettner and Stefan Naeher, chapter 65 of the Handbook of Discrete and Computational Geometry, Goodman and O'Rourke editors, 2nd Edition, 2004
A good introduction to generic programming: Generic Programming and the STL: Using and Extending the C++ Standard Template Library, Matthew H. Austern, Addison Wesley Professional, 1999

16.3.2005 Number types, Ron Wein

30.3.2005 Envelopes

Guest talk: Applied Geometry in GIS, Eran Leiserowitz, Telmap Ltd.

6.4..2005 Envelopes, continued

13.4.2005 Point location, Idit Haran

20.4.2005 Geometric rounding

4.5.2005 Observers, visitors and adaptors:

18.4.2005 Controlled perturbation

25.4.2005 Dynamic maintenance of molecular surfaces under conformational changes (ppt file), Eran Eyal

1.6.2005 Motion planning and related applications of arrangements