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
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 geometriccomputing 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 motionplanning algorithms
geometric modelling of molecules
The course is geared towards graduate students in computer science. Thirdyear 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 largescale 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
LEDA
CORE
The Boost Graph Library (BGL)
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
THE END