Joe Mitchell -Stony Brook University

Geometric Shortest Path and Optimal Network Problems:
Some Recent Results and Continuing Challenges

Abstract: What is the best strategy for mowing one's lawn? How should a traveling salesperson visit a set of cities or regions while traveling the shortest distance? How should a robot move efficiently within a building in order to be able to see every nook and cranny? What is the best strategy to "unfreeze" your teammates in a game of freeze-tag? How should an industrial milling tool be guided in order to shape a particular part? Where should security cameras be placed in order to provide robust surveillance of an airport terminal?

These are all examples of shortest path and network optimization problems that arise in geometric settings and are studied within the field of computational geometry. Almost all versions of these problems are provably hard, from the point of view of complexity of algorithms, so our efforts often focus on solving special cases exactly, devising approximation algorithms that have some provable performance guarantee, and designing heuristic methods that have good experimental behavior in practice. We survey some of our recent work on geometric optimization of paths, tours, and networks, with applications in robotics, sensor networks, vehicle routing, and manufacturing. We will highlight several outstanding open problems under current investigation.

Colloquium - 16:00

Maike Buchin -Freie Universität Berlin

Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard

Abstract: Given a set of points sampled from a smooth surface in R³ we want to find a "good" triangulation of the points in the sense that the triangulation resembles the underlying surface. This can be done by locally minimizing a given cost function. One such cost function is the total absolute discrete Gaussian curvature. Alboul and van Damme first suggested this for post-processing of polyhedral surfaces using a simple flip heuristic.

This heuristic however can get stuck in local minima and it remained an open question, whether an efficient algorithm exists which always finds the global minimum. In this talk we show that, in the case of terrains, minimizing the total absolute Gaussian curvature is NP-hard.

This is joint work with Joachim Giesen, ETH Zurich.