Colloquium

Date: October 13, 2022

Time: 4:00PM - 5:00PM

Location: Bloc 117

Speaker: Chris Bishop, Stony Brook University

Description: Title: Optimal Triangulation of Polygons
Abstract: It is a long-standing problem of computational geometry to triangulate a polygon using the best possible shapes, e.g., to minimize  the maximum angle used (MinMax), or maximize the minimum angle (MaxMin).   Besides the problem's intrinsic interest, well formed meshes give better results in various numerical algorithms, such as the finite element method.  If we triangulate using only diagonals of the polygon, then there are only finitely many possible triangulations and the famous Delaunay triangulation solves the MaxMin problem. When extra vertices (Steiner points) are allowed,  the set of possible triangulations becomes infinite dimensional, but I recently proved that  the optimal angle bounds  for either the MinMax or MaxMin  problems can be easily computed, and are (usually) attained by some triangulation.   I will prove some previously known necessary conditions on the angle bounds using  Euler's formula for planar graphs,  and briefly describe the new theorem that they are also sufficient; the proof of this  uses conformal and quasiconformal mappings, but our discussion is independent of the previous lecture.  Several  surprising consequences  follow, and many related problems remain open.