9th Winter School on Computational Geometry

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
  • Homotopy (after download change name to homotopy.key)

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.
  • Time-Space Trade-off
    quick introduction to the model and discussion of last result for computing Voronoi diagrams of high order and its applications to other problems
  • Time-Space Trade-offs for Triangulating a Simple Polygon
  • Time-Space Trade-offs for Computing (High Order) Voronoi Diagrams