Title: Optimal triangulation of polygons

Speaker: Chris Bishop, Stony Brook University

Date and time: 6pm (New York time), Tuesday, February 28, 2023

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

...and on Zoom, details on the seminar mailing list

It is a long-standing problem to triangulate a polygon using the best possible shapes, e.g., to minimize the maximum angle used (MinMax), or maximize the minimum angle (MaxMin). If we triangulate using only diagonals of the polygon, then there are only finitely many possible triangulations, and the Delaunay triangulation famously solves the MaxMin problem. When extra vertices (Steiner points) are allowed, the set of possible triangulations becomes infinite dimensional, but it turns out that the optimal angle bounds for either the MinMax or MaxMin problems in this case can be computed in linear time, and that these bounds are (usually) attained by some finite triangulation (which need not have a polynomial complexity bound). Several surprising consequences follow from the proof, and many related problems remain open.