Optimal Triangulation of Polygons
摘要
How do we cut a polygon into triangles that are all as “round” as possible, e.g., minimizing the maximum angle used? In this paper, we compute the optimal upper and lower angle bounds for triangulating an N-gon P with Steiner points, sharpening the 1960 theorem of Burago and Zalgaller that every polygon has an acute triangulation. For any polygon, we show both the upper and lower bounds can be computed in linear time from the list of interior angles of the polygon. We also show that both types of optimal bound are usually attained by some finite triangulation of the polygon (but sometimes they cannot both be attained by a single triangulation). We do not address the interesting problem of finding efficient triangulations that attain the optimal angle bounds; even in some simple cases, our construction gives many more triangles than are actually needed. The exceptional polygons where the optimal bounds can only be approximated, but not attained, are easily described: if and only if every interior angle is an integer multiple of