This course will survey some of the most recent algorithmic paradigms and data structures that have led to the latest advances in the state of the art of computational geometry.
Erin W. Chambers: Some Recent Trends in Computational Topology
Computational topology is an emerging area which is growing from the increasing need for algorithms that are rooted in the tools and techniques of topology; it has proven useful for a variety of areas such as data analysis, mesh reconstruction, biological modeling, and GIS analysis. The two primary tools for algorithms in computational topology are homotopy and homology, both of which capture topological invariants of the shape, such as the number of handles or voids, rather than focusing on the geometry of the structure. While homotopy is a more complete invariant of the shape, it is also much harder to compute, and hence there is a large body of work that relies on the coarser invariant of homology. In this course, I will introduce these fundamental concepts and then cover a few recent trends in more depth, including: algorithms to compute persistent homology of a point set or simplicial complex; the crust algorithm and its descendants for surface reconstruction; algorithms on surface embedded graphs for fundamental combinatorial problems such as flows and cuts; and algorithms to compute similarity measures for curves and surfaces.
Download the notes for this course (updated on April 18) – Download slides
Nabil Mustafa: Local Search in Geometry: Samples, Separators and Subdivisions
Local-search is an intuitive approach towards solving optimization problems: start with any feasible solution, and try to improve it by local operations. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution; in fact, for purely graph-theoretic problems it is often easy to construct instances where local search algorithms fail to find even approximately good solutions.
A key realization in the last several years has been the effectiveness of local search for geometric problems, leading to the resolution of a series of long-standing open computational geometry problems. The underlying reason for effectiveness of local search in geometric problems is the existence and interplay between three compact structures: separators, random samples, and spatial subdivisions.
In this course, I will present the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for three types of geometric problems: combinatorial (e.g., geometric independent set, geometric set cover and hitting set), Euclidean (the very recent breakthroughs in algorithms for k-means, k-median) and metric.
Lecture 1. The basic tools: Separators, Sampling and Subdivisions
Lecture 2. Combinatorial Local Search
Lecture 3. Euclidean Local Search
Lecture 4. Metric Local Search
Lecture 5: Other recent breakthroughs in geometric combinatorial optimization
Download a preliminary version of the notes for this course
There will be two lectures every morning, respectively 2h and 1h 30min long. In the afternoons, attendees and lecturers will work together in open problems. There will be a seminar talk every afternoon.
– Lectures and seminar talks will take place in the Auditorium.
– Working and interacting will take place in rooms Pol1 and Pol2.