9th Winter School on Computational Geometry

9th Winter School on Computational Geometry


9th Winter School on Computational Geometry

March 1-6, 2017

9th winter school time table

9th winter school time table
9:00-10:00 10:00-10:30 10:30-11:30 11:30-12:00 12:00-13:00 13:10-13:40
March 1th
Jeff Erickson Coffee break Maike Buchin Coffee Break Matias Korman lunch
March 2nd
Matias Korman Maike Buchin Matias Korman
March 3th
Jeff Erickson Maike Buchin Matias Korman
Saturday No Lecture
March 5th
Jeff Erickson Coffee break Matias Korman Coffee break Maike Buchin lunch
March 6th
Jeff Erickson Matias Korman Maike Buchin

Lecture Subjects

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.

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