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 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.
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