Applied Geometric Computing and CGAL
Spring 2005
(0368.4073.01)

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)

http://www.cs.tau.ac.il/~danha/courses/agc-cgal05.html

The final project, due August 10th, 2005

Assignments

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
LEDA
CORE
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

part 1 - Generic Programming and STL
part 2 - CGAL (Upper Convex Hull)

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: