Improved bounds for acute triangulations of convex polygons. (English) Zbl 1292.52003

Zamfirescu, Carol T.

Util. Math. 91, 71-79 (2013).

This paper concerns right and acute triangulations of convex planar polygons. By definition, a triangulation of a polygon \(P\) is referred to as acute (non-obtuse), if in each appearing triangle all angles are acute (acute or right respectively). Similarly, a triangulation of \(P\) is referred to as right, if each triangle is right, i.e. has two angles acute and one right. The question is to estimate the number of triangles necessary for acute (right, non-obtuse) triangulations of convex polygons.
It is known that any obtuse triangle can be triangulated into seven acute triangles, and this estimate is optimal, see Yu. D. Burago and V. A. Zalgaller [Vestn. Leningr. Univ., Mat. Mekh. Astron. 15, No. 2, 66–80 (1960; Zbl 0098.35403)]. As well, any convex quadrilateral can be triangulated with at most nine acute triangles, see [H. Maehara, Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2098, 237–243 (2001; Zbl 0998.52005)]; any convex pentagon can be triangulated with at most 54 acute triangles, see [L. Yuan, Bull. Math. Soc. Sci. Math. Roum., Nouv. Sér. 53(101), No. 4, 393–410 (2010; Zbl 1240.52004)]; for convex hexagons the best estimate for the number of triangles necessary for acute triangulations is 9420, cf. [L. Yuan, Discrete Comput. Geom. 34, No. 4, 697–706 (2005; Zbl 1112.52002)]. The mentioned bounds seem to be far from being optimal, especially for the case \(n\geq 6\). The paper is aimed to diminish the bounds, the following results are proved.
Theorem 1. Let \(P\) be a planar convex \(n\)-gon with \(n\geq 6\). Then \(P\) admits a right triangulation of size at most \[ r_n=\frac{2}{3}n^3+n^2-\frac{47}{3}n+22. \]
Theorem 2. Let \(P\) be a planar convex \(n\)-gon with \(n\geq 6\). Then \(P\) admits an acute triangulation of size at most \[ a_n=\frac{2}{3}n^3+2n^2-\frac{71}{3}n+28 \] for even \(n\) and \[ a_n=\frac{2}{3}n^3+2n^2-\frac{101}{3}n+88 \] for odd \(n\).
Double convex \(n\)-gons, viewed as degenerated convex polyhedra, are considered too. It is proved, that any double convex \(n\)-gon with \(n\geq 6\) admits a right triangulation of size at most \(2r_n\) and an acute triangulation of size at most \(2a_n\).

Reviewer: Anatoliy Milka (Kharkov)

MSC:

52A10	Convex sets in \(2\) dimensions (including convex curves)
52C20	Tilings in \(2\) dimensions (aspects of discrete geometry)
52B05	Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

Keywords:

polygon; acute triangulation; right triangulation; double polygon

Citations:

Zbl 0098.35403; Zbl 0998.52005; Zbl 1240.52004; Zbl 1112.52002