Talk given in NYU CG seminar on 4/11/23.

Abstract: 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.