Optimal angle bounds for Steiner triangulations of polygons

For any simple polygon P we compute the optimal upper and lower angle bounds for triangulating P with Steiner points, and show that these bounds can be attained (except in one special case). The sharp angle bounds for an N -gon are computable in time O(N ), even though the number of triangles needed to attain these bounds has no bound in terms of N alone. In general, the sharp upper and lower bounds cannot both be attained by a single triangulation, although this does happen in some cases. For example, we show that any polygon with minimal interior angle θ has a triangulation with all angles in the interval I = [θ, 90 • -min(36 • , θ)/2], and for θ ≤ 36 • both bounds are best possible. Surprisingly, we prove the optimal angle bounds for polygonal triangulations are the same as for triangular dissections. The proof of this verifies, in a stronger form, a 1984 conjecture of Gerver.