Assoc. Prof. Dr. Sergio Cabello
Faculty of Mathematics and Physics, University of Ljubljana
Ljubljana, Slovenia
Email: sergio.cabello@fmf.uni-lj.si
Homepage: http://www.fmf.uni-lj.si/~cabello/
Title: Two Applications of Geometric optimization
Author(s): Sergio Cabello
Abstract: In this talk we will encounter two unrelated problems in the area of Geometric Optimization and some of the algorithmic ideas leading to their efficient solution. The work reported has been done recently with Drago Bokal, David Eppstein, Panos Giannopoulos and Lazar Milinkovic. Motivated by sensor networks, we will discuss the following minimum separation problem: given a set of disks in the plane and two points s and t, not covered by any of the disks, compute the minimum number of disks one needs to retain so that any path connecting s to t intersects some of the retained disks. Motivated by trajectory analysis, we will discuss the following problem: given a sequence of points in the plane describing a trajectory, find all maximal subtrajectories with a prescribed hereditary property, like for example, having diameter one.
Invited by Slovenian Society Informatika, Section of Operations Research.