<p>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 <i>N</i>-gon <i>P</i> 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(60^\circ \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>60</mn> <mo>∘</mo> </msup> </math></EquationSource> </InlineEquation>, and some pair of sides has irrational length ratio. We also show that the optimal angle bounds for polygonal triangulations are the same as for triangular dissections. This implies, in a stronger form, a 1984 conjecture of Gerver. Although the statements of our results involve only Euclidean geometry, the proofs depend on conformal and quasiconformal techniques.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal Triangulation of Polygons

  • Christopher J. Bishop

摘要

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 \(60^\circ \) 60 , and some pair of sides has irrational length ratio. We also show that the optimal angle bounds for polygonal triangulations are the same as for triangular dissections. This implies, in a stronger form, a 1984 conjecture of Gerver. Although the statements of our results involve only Euclidean geometry, the proofs depend on conformal and quasiconformal techniques.