Geometry Seminar

Finding Diverse Triangulations and Geometric Knapsacks

Speaker: Mayank Goswami, Queens College, CUNY

Location: Warren Weaver Hall 1314

Date: Tuesday, April 16, 2024, 6 p.m.

Synopsis:

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.

Notes:

In-person and on Zoom. See mailing list announcements for Zoom details or contact Boris Aronov.