Applied Geometric Computing and CGAL, Spring 2005

Applied Geometric Computing and CGAL

0368.4073.01

Lecture: Wednesday 16-19, Schreiber 7

Instructor: Dan Halperin
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)

The final project, due August 10^th, 2005

Assignments

More information for the assignments (by the TA)

1. Assignment no. 1 [pdf], due: March 30th, 2005
2. Assignment no. 2 [pdf], new due date: May 11th, 2005
   • More information on Exercise 2.3 [pdf]
3. Assignment no. 3 [pdf], due: June 1st, 2005

Preparing for class

for the class on 20/4: Snap rounding [pdf]

for the class on 4/5

• In class we will discuss software design issues that come up in the CGAL Arrangements package. We will review observers and visitors (see the book Design Patterns) and the generic programming version of adaptors (see the book on Generic Programming). A concrete adpator that will be discussed relates the basic arrangement representation in CGAL with graphs from the BOOST Graph Library
• Design Patterns
  Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Addison-Wesley, 1995
• Generic Programming and the STL: Using and Extending the C++ Standard Template Library
  Matthew H. Austern, Addison-Wesley, 1999
• The Boost Graph Library User Guide and Reference Manual
  Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine, Addison-Wesley, 2002

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.02.2005 Introduction
• 02.03.2005 Arrangements—overview [psz]
• 09.03.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
    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.03.2005 Number types, Ron Wein [psz]
• 30.03.2005 Envelopes [psz]
  Guest talk: Applied Geometry in GIS, Eran Leiserowitz, Telmap Ltd.
• 06.04.2005 Envelopes, continued
• 13.04.2005 Point location, Idit Haran [ppt]
• 20.04.2005 Geometric rounding [psz]
• 04.05.2005 Observers, visitors and adaptors:
  • The new design of the CGAL arrangement package, Ron Wein [psz]
  • Aadapting CGAL arrangements to BOOST graphs, Efi Fogel [psz]
• 18.04.2005 Controlled perturbation [psz]
• 25.04.2005 Dynamic maintenance of molecular surfaces under conformational changes, Eran Eyal [ppt]
• 01.06.2005 Motion planning and related applications of arrangements [psz]

THE END