Improved bounds for acute triangulations of convex polygons.

*(English)*Zbl 1292.52003This 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\).

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)