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 CG called geometric knapsack.
Finding Diverse Triangulations and Geometric Knapsacks
Mayank Goswami (CUNY)
Tuesday, April 16th, 6pm ET, Room 1314, Warren Weaver Hall, NYU
(also on Zoom)