Applied Geometric Computing and CGAL
The final project, due August 10th, 2005
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.
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
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
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.
CGAL's global site,
CGAL @ TAU
Robust geometric computing at TAU
The Boost Graph Library (BGL)
2.3.2005 Arrangements - overview
9.3.2005 Introduction to generic programming and CGAL, Efi Fogel
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
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