Abstracts for the lectures:

• Helmut Alt   (Freie Universität Berlin):   Geometric methods in shape comparison and matching
  The lecture will present methods from computational geometry for the comparison and matching of planar shapes that are represented by polygonal or other piecewise algebraic curves. We will consider several distance measures to describe similarity between shapes, in particular the Hausdorff- and the Fréchet- distance. Algorithms for measuring the distance between two shapes will be presented. Also the problem of matching shapes optimally with respect to a given distance measure will be considered. There are different variants of this problem depending on the set of allowable transformations, like translations, rigid motions, similarities etc. Also a few generalizations to three and higher dimensions will be presented.

• Tamal Dey   (The Ohio State University) :   Computing Shapes and Their Features from Point Samples
  Recent advances in scanning technology and scientific simulations can generate sample points from a geometric domain at ease. Inferring the shape and their features from such simple light-weight input can be a very effective modeling paradigm across many areas of science and engineering. In this tutorial we will go over the techniques developed for such modeling paradigms. In particular, we cover an algorithm called Cocone for surface reconstruction from point clouds. This algorithm has theoretical guarantees and has been successfully implemented. We will go over its analysis and some of its variants to handle practical data sets. Often, the input point clouds suffer from undersampling causing too few points and oversampling causing too many points. We discuss techniques to deal with these two anomalies.

  After discussing reconstructions we will go over algorithms that extract features of the sampled shapes from their point samples. This will include algorithms for extracting shape dimensions, their medial axes and so-called feature segments from point cloud data.

  Most of the presentations will not require any special background except that a good knowledge about Delaunay and Voronoi geometry and some preliminary concepts about algebraic and differential topology are required. For further information on the topics, see http://www.cis.ohio-state.edu/~tamaldey/geohome.html. There are also slides of the lecture of Tamal Dey available.

• Günter Rote   (Freie Universität Berlin):   Pseudotriangulations in Computational Geometry
  A pseudotriangulation is a decomposition of the plane into pseudotriangles, polygons with exactly three convex vertices and an arbitrary number of concave vertices. Pseudotriangulations recently emerged as a data structure with a variety of applications: visibility complexes, ray shooting, robot arm motion planning, kinetic collision detection, guarding, reflex-free hulls, etc. I will survey some of the algorithmic, geometric and combinatorial properties of pseudotriangulations.

  Here you may find course material and exercises for the course of Günter Rote.

• Gert Vegter   (University of Groningen):   Introduction to Computational Topology
  Topology studies global properties of geometric objects, like the number of connected components, tunnels, and cavities. It also deals with problems concerning the existence of continuous, shape-preserving deformations of geometric objects like curves and surfaces. Computational topology deals with the complexity of such problems, and with the design of efficient algorithms for their solution. During this course, we present the basic ideas and methods of computational topology in two sessions.

  Course material will be provided in the form of sheets and handouts with exercises, available before the start of the fall school. Doing the exercises will enable you to grasp the basic ideas, fill in the details necessarily skipped during the lectures, and prepare the way for further study.

  Course Material is available on http://www.cs.rug.nl/~gert/topology.html.

  Session 1 (60 minutes): Simplicial complexes and their homology.

  In discrete and computational geometry surfaces can be subdivided into (curvilinear) triangles, and 3D regions with polyhedral boundaries can be subdivided into tetrahedra. More generally, in any dimension simplicial complexes provide a class of geometric objects suitable for topological computation. For this class of objects we introduce topological invariants like simplicial homology groups and Betti-numbers, and consider the relation with well-known combinatorial numbers like the Euler characteristic. We also present algorithms for the computation of Betti-numbers.

  Session 2 (60 minutes): Morse theory.

  Morse theory provides a way to decompose geometric objects like surfaces (or, in higher dimensions, manifolds) into simple cells. Crucial for this approach are the singularities and level-sets (or, contours) of well-behaved real valued functions defined on such a surface, like the height function of a polyhedral terrain. The methods from Morse theory usually yield subdivisions with a much smaller number of cells than the number of triangles (cells) in a curvilinear mesh on the surface (manifold). This decomposition contains information on the homology of the manifold.