# 9th Winter School on Computational Geometry

## 9th Winter School on Computational Geometry

#### Maike Buchin

• Algorithms for comparing curves and surfaces using the Frechet distance
• Algorithms for curves
• Finding good matchings
• Approximation algorithms
• Applications to Analysis of Trajectories
• Lower bounds
• Algorithms for surfaces

#### Jeff Erickson

• Homotopy in the plane
Consider a planar environment with polygonal obstacles. Two paths in this environment are HOMOTOPIC if one can be continuously deformed into the other without intersecting the obstacles. In this first lecture, I will discuss two key algorithm problems related to homotopy. First, given two paths, decide whether they are homotopic. Second, given a single path P, find the shortest path that is homotopic to P.
• Surface maps
In the second lecture, I will describe standard data structures and structural properties of planar decompositions and of embeddings of graphs on topological surfaces. Specific topics include rotation systems, duality, tree-cotree decompositions, Euler’s formula, systems of loops and polygonal schemas, and homotopy and homology on surfaces.
• Short interesting cycles
In the third lecture, I will describe fast algorithms for finding shortest topoligically interesting cycles, minimum cuts, and other optimal structures in surface graphs. As a key ingredient, I will describe an algorithm for the multiple-source shortest path problem, which asks for an implicit encoding of all shortest path distances where one of the vertices lies on a particular face.
• Surface homotopy
In the fourth lecture, I will return to basic questions about continuous deformation of curves on surfaces. I will describe a modern implementation of an algorithm of Max Dehn, first described in 1916, to decide if one curve on a surface can be continuously deformed into another. I will also sketch an algorithm to find the shortest path homotopic to a given path.
• Untangling curves
In the final lecture, I will return to basic questions about deforming curves in the plane. Any closed curve in the plane can be continuously deformed into a SIMPLE closed curve using a finite sequence of local transformations called homotopy moves. But how many such moves are required? I will describe an algorithm that uses at most O(n^{3/2}) moves, and prove that this bound is optimal in the worst case. I will also discuss extensions of this problem to more complex surfaces, and connections to Delta-Y reduction of planar graphs.
• Algorithms for Comparing Curves and Surfaces(Introduction and classical algorithms)
• Algorithms for Comparing Curves and Surfaces(Other ways of searching the free space)
• Algorithms for Comparing Curves and Surfaces(Lower Bounds)
• Algorithms for Comparing Curves and Surfaces(Finding a middle curve)

#### Matias Korman

• Consistent Digital Segments in two dimensions
An introduction to the concept of consistent digital segments and a survey in the known results for the two dimensional case
• Consistent Digital Segments in higher dimensions
In this session I will further explore the concept of CDS and discuss the difficulties of higher dimensions
• Extremal distances in simple polygons
Introduction to simple polygons, extremal distances (center and diameter), as well as the state-of-the-art algorithms for finding center and diameter
• Extremal distances in polygonal domains
Extension of the topics of the third talk to polygonal domains and highlight of why such a small change in the environment makes the problem so difficult.