Data-Structures and Paradigms in Computational Geometry

Computational Geometry (CG) is a field wherein data structures to represent geometrical objects play an important role. Also some particular paradigms are used frequently in CG. The course "Datastructures and Paradigms in Computational Geometry" is dedicated to this aspect of doing geometry by computer.

Currently a $C++$ library of algorithms for Computational Geometry called CGAL is built at RISC-Linz in cooperation with 6 other universities in Europe and Israel. Since only few attempts were made before to build such a library, CGAL is a good reference for the latest developments in the area of CG. Experiences gained recently in the development process of CGAL form a basis for this course.

The content of the course:

• An introduction to overall design of and the tools used in CGAL, and motivations which led to the choice of this particular design and these particular tools.
• Several objects developed in CGAL (like CGAL_Triangle, CGAL_Iso_rectangle, CGAL_Polygon, CGAL_Object, and CGAL_Planar_map) will be presented.
• Data structures for performation of Boolean Operations on polygons and polyhedra (like DCEL, 3-hyper map) will be discussed.
• The CG-typical sweepline paradigm will be presented, emphasizing on the example of detection and reporting intersection of two simple polygons.
• The CG-typical concept of triangulations (in particular the Delaunay triangulation, and in CGAL) will be presented.
• A brief look will be taken at some other things covered by CGAL (GIS, Optimization problems in Geometry).
• Some application domains will be treated:
  • NURBS,
  • Robot Motion Planning: Voronoi Diagram, Visibility Graph, Manhattan Distance Wavefront Approach, and their relationship; the car-like robot, without and with trailers.
• Several demo's are foreseen (CGAL, Cinderella for Projective Geometry, bfp motion planning for car-like robots).