7th Winter School on Computational Geometry

7th Winter School on Computational Geometry

7th Winter School on Computational Geometry

February 25 - March 2, 2015


7th winter school time table

5th winter school time table
9:00-10:00 10:00-10:20 10:20-11:20 11:20-11:40 11:40-12:40 12:40-14:00
Feb. 25 David Mount Coffee break Wolfgang Mulzer Coffee break Jason O'Kane Lunch
Feb. 26 David Mount Wolfgang Mulzer Jason O'Kane
Feb. 27 David Mount David Mount Wolfgang Mulzer
Feb. 28 No Lecture
Mar. 1 Wolfgang Mulzer Coffee break David Mount Coffee break Jason O'Kane Lunch
Mar. 2 Jason O'Kane Jason O'Kane Wolfgang Mulzer
David Mount
  • Lecture 1: Point Location: Entropy and Expected-case Efficiency
  • Lecture 2: Well-Separated Pair Decompositions and Applications
  • Lecture 3: Approximation Algorithms for Euclidean Minimum Spanning Trees
  • Lecture 4: Data Structures for Approximate Nearest Neighbor Searching
  • Lecture 5: Approximate Nearest Neighbor Searching and Polytope Approximation
Wolfgang Mulzer
  • Lecture 1
    • Title: Computational Geometry with Bounded Workspace: Model and Basics
    • Abstract:
      In many applications in modern computing the size of the input far exceeds the amount of available workspace. I will present a computational model that tries to capture this situation, and I will illustrate the model with a few simple examples.
  • Lecture 2
    • Title: Computational Geometry with Bounded Workspace: Basic Algorithms
    • Abstract:
      I will show how to solve some basic geometric problems in the constant workspace model from the previous lecture: computing the convex hull, triangulating a planar point set, finding the Euclidean minimum spanning tree, finding a shortest path in a polygon.
  • Lecture 3
    • Title: Computational Geometry with Bounded Workspace: Advanced Algorithms and Time-Space Trade-offs
    • Abstract:
      I will describe how to triangulate a simple polygon using constant workspace. Then I will present a general method for achieving time-space trade-offs for geometric problems.
  • Lecture 4
    • Title: Computational Geometry with Bounded Workspace: More on Time-Space Trade-offs
    • Abstract:
      I will present more instances where time-space trade-offs for geometric problems can be achieved, e.g., triangulating a histogram, finding shortest paths in a polygon, triangulating a point set, and more.
  • Lecture 5
    • Title: Computational Geometry with Bounded Workspace: Complexity Theory and Lower Bounds
    • Abstract:
      In the final lecture, I will Lecture about the complexity theoretic foundations of algorithms with bounded workspace and about techniques for showing lower bounds for them.
Jason O'Kane

Series title: Automated Filtering and Planning for Simple Robots

  • Lecture 1. Information states: Coping with incomplete information
  • Lecture 2. Planning without sensors: Manipulation, localization, and navigation
  • Lecture 3. Visibility-based pursuit and evasion
  • Lecture 4. Combinatorial filters
  • Lecture 5. Navigation planning for unreliable robots