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 10th, 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

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

AGC-GCAL05, Final project

Below you’ll find a list of topics for possible final projects. You have a lot of freedom in choosing a project and you are encouraged to suggest your own topic based on your thesis research, industry experience, or simply your interest. You may also propose variations on the themes below.

By June 15th 2005, you have to submit a one page proposal for approval by the instructor. The submission date of the final project is August 10th 2005 . (For every day of delay you will be fined 3 points out of 100.) Notice that in addition to submitting the project to Idit Haran you need to fix a meeting for an oral exam with Danny (on the project and the course) during the week following the submission deadline.

Every project should include an implementation with (simple) graphic interface, and accompanying text explaining the solution and the implementation.

Do not undertake huge projects. (As you may have learned during the semester, geometric problems seem simpler than they actually are when it comes to implementation.) In particular you may propose partial solutions to the projects proposed here—the part you plan to solve however should be clearly stated in the brief proposal document. It’s better that you’ll opt for a smaller project and do it thoroughly including extensive experimentation, careful testing, comparison with other solutions experimentally and theoretically (where applicable).

Good luck!

Project topics

  • controlled perturbation for lower envelopes of segments
  • implementing output-sensitive snap rounding for segments as in the paper:
    An intersection-sensitive algorithm for snap rounding
    M. de Berg, D. Halperin and M. Overmars
  • snap rounding arrangements of circles
  • adapting graph algorithms from BOOST to CGAL arrangements
  • exact arrangements of arcs of great circles on a sphere
  • controlled perturbation for arrangements of little circles on a sphere

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content