.png){kind=icon}
.png){kind=icon}
Return
Optimal Triangulation of Polygons
.png){kind=icon}
PRE
AI
DOI：10.1007/s00454-026-00831-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 degrees\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$60<^>\circ $$\end{document}, 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.
Keywords:
Acute triangulation
Steiner points
Dissections
Schwarz-Christoffel formula
Quasiconformal mappings
Delaunay triangulation
Journal
D
IF:
0.6
Papers:
62
Citations:
0