LFCS Seminar: Tuesday 03 September - Mayank Goswami

Title: Finding Diverse Triangulations and Geometric Knapsacks

Abstract: 

Many algorithms and heuristics in computational geometry start with a triangulation of some given domain. We restrict ourselves to polygons and ask: given a polygon P and a number k, how fast can one generate k triangulations of P that look as different from each other as possible? Moreover, for many applications we don't just want any triangulation, but a "nice" one. For example, we may want a triangulation that has small (Euclidean) length, or is close to a Delaunay triangulation., etc. How fast can we generate k different-looking, nice triangulations? In this talk we will see a simple but fairly general technique called diverse dynamic programming, that solves the above problems for finding diverse triangulations approximately. We also apply the technique to two popular variants of another problem in computational geometry called geometric knapsack, and other problems on planar graphs.

Bio:

Mayank Goswami is an Associate Professor at the City University of New York. Prior to this he was a postdoc at the Max-Planck Institute for Informatics. He completed his PhD in applied mathematics from Stony Brook University. Mayank's main research interests are algorithm design (instance optimal sorting and searching, graph problems, I/O efficient algorithms, lower bounds) and in computational geometry and algorithms for geometric databases. His secondary research interests are theoretical machine learning and applied complex analysis.