Date:           Mon, 24 Feb 1997 12:28:48 MET
From:           DMANET <dmanet@math.utwente.nl>
Reply-To:       theosekr@inf.fu-berlin.de
To:             DMA-LIST@NIC.SURFNET.NL
Subject:        Summer School Computational Geometry '97

---

Graduate Program "Computational Discrete Mathematics"
Graduiertenkolleg "Algorithmische Diskrete Mathematik"

---

In connection with the Graduate Program "Computational Discrete Mathematics" (Graduiertenkolleg "Algorithmische Diskrete Mathematik"), a

Summer School
on
Computational Geometry

The program will be presented by the following five lecturers:

• Helmut Alt, Freie Universität Berlin
  Geometric Algorithms for Matching Point Patterns and Shapes

  Matching of point patterns and of shapes is a central problem in computer vision and image processing. Geometric methods for this task have been investigated within computational geometry during the last ten years and numerous algorithms have been developped for its different variants. The lecture will give a survey of these ideas and algorithms. In particular, we will discuss different distance measures to be used in order to compare shapes and consider different transformations in order to match the input figures. The latter include translations, Euclidean motions, similarities, and arbitrary affine transformations. We will also consider several applications of these methods,for example in astronomy, medicine and archaeology.

• Herbert Edelsbrunner, University of Illinois
  Smooth Shapes and Deformation

  A representation of geometric shapes using a complementing pair of data structures is introduced. It consists of a complex representing connectivity information and a smooth surface serving as the appearance of the shape. Properties of the representation related to questions in geometric modeling and deformation are discussed.

• Rolf Klein, FernUniversität Hagen
  On-Line Algorithms

  Often one needs to make a decision on-line, i.e. with information about the past and the present only, but without complete information about the future. Examples are job scheduling, paging, self-organizing data structures, or a robot exploring an unknown terrain. If the future were fully known one could take optimal decisions. Without this knowledge, error can, in general, not be avoided, resulting in a solution that is less than optimal. An on-line algorithm A for solving a problem P is called competitive with factor c if, for each instance p in P, the cost of solving p by algorithm A on line does not exceed c times the cost of solving p optimally. In this lecture we are studying various problems that admit competitive on-line solutions. The algorithms themselves are extremely simple, even though computing an optimal solution may be difficult, perhaps NP-hard. Sometimes it is even possible to determine the on-line complexity of a problem P, i.e. the smallest factor c achievable by an on-line algorithm.

• Kurt Mehlhorn, Max-Planck-Institut für Informatik
  On the Implementation of Geometric Algorithms

  We discuss issues arising in the implementation of geometric algorithms and illustrate them on the basis of the LEDA platform of combinatorial and geometric computing.

  Degeneracies: Papers in computational geometry usually assume that inputs are in general position. This assumption causes some difficulties for implementers. We discuss two approaches to degeneracies: redoing the theory and perturbation.

  Precision: The use of floating point arithmetic in geometric computations has led to many disasters in the implementation of geometric algorithms. We discuss efficient implementations of exact arithmetic for geometric computations: Integers with floating point filters and rationals closed under square roots.

  Checking: Many geometric algorithms are complex and it is easy to make mistakes during their implementation. We discuss checkers for geometric programs.

  Case Studies: We show some programs as case studies.

• Günter Rote, Technische Universität Graz
  Realization of Three-Dimensional Polytopes

  Various questions can be asked about three-dimensional polytopes.

  Given an combinatorial type of polytope (a three-connected planar graph), is there a polytope with this structure such that all vertices lie on a sphere (Inscribable polytopes)? ...Such that all faces are tangent to a sphere (Circumscribable polytopes)? ...Such that all edges are tangent to a sphere? Is a polytope uniquely determined by the distance (on the polytope) between every pair of vertices?

  With each of these questions there is an associated algorithmic question of actually constructing the polytope in question. Some of these questions have classical answers, others were only recently solved, some are still unsolved.

Each lecturer will present a lecture of two hours. In addition, exercises will be handed out, solved in small groups and discussed later in special sessions.

The Summer School will take place in Chorin, a picturesque site near the ruins of an old monastery about 50 km northeast of Berlin. The costs per participant are DM 150,00 and include transportation between Chorin and Berlin and full board during the Summer School. The number of participants is limited to about 25. Applications with a short curriculum vitae (incl. scientific background) and a short letter of recommendation of a university faculty member should be sent to:

Prof.Dr.Helmut Alt
Sommerschule '97
FB Mathematik und Informatik, Institut für Informatik
Freie Universität Berlin
Takustrasse 9
D-14195 Berlin

until 19th April 1997. Further information can be obtained from Hannah Heinrich (phone: 030/838 75 103; e-mail: theosekr@inf.fu-berlin.de).