References

• M. Bern and D. Eppstein. Polynomial size non-obtuse triangulation of polygons. Proc. 7th ACM Symp. Comp. Geom., 1991, pp. 342-350; Int. J. Comp. Geom. & Appl., vol. 2, 1992, pp. 241-255. Shows that any simple polygon can be triangulated with O(n²) non-obtuse triangles.

• M. Bern, D. Eppstein, and J. Gilbert. Provably good mesh generation. Proc. 31st IEEE Symp. Foundations of Comp. Sci., 1990, vol. I, pp. 231-241; J. Comp. Sys. Sci., vol. 48, 1994, pp. 384-409. Figure 5 of the journal version includes a tile (labeled bbbb) triangulating the square with all angles at most 80 degrees.

• M. Bern, S. Mitchell, and J. Ruppert. Linear-size non-obtuse triangulation of polygons. Proc. 10th ACM Symp. Comp. Geom., 1994, pp. 221-230; Disc. Comp. Geom., vol. 14, 1995, pp. 411-428.

• Charles Cassidy and Graham Lord. A square acutely triangulated. J. Rec. Math., vol. 13, no. 4, 1980/81, pp. 263-268.

  Summary (from Math. Reviews 84j:51036): We examine the problem of triangulating the square into acute-angled triangles. By a proper triangulation we mean a subdivision of the square and its interior into nonoverlapping triangles in such a way that any two distinct triangles are either disjoint, have a single vertex in common, or have one entire edge in common; and by an interior vertex we mean a vertex (of a triangle) which lies inside the square but not on its boundary. We begin with a proof, alternative to that of Lindgren, of the minimality-uniqueness of eight. Then we show there is no triangulation into nine triangles! And finally we demonstrate that there is a triangulation of the square into n acute-angled triangles for all n greater than or equal to ten.

• J. L. Gerver. The dissection of a polygon into nearly equilateral triangles. Geom. Dedicata, vol. 16, 1984, pp. 93--106. Shows how to compute a dissection of a polygon (that is, vertices embedded within sides of triangles are allowed) with no angles larger than 72 degrees, assuming all interior angles of the input measure at least 36 degrees.

• H. Lindgren. Austral. Math. Teacher, vol. 18, 1962, pp. 14-15. Cited by Cassidy and Lord.

From the Geometry Junkyard, computational and recreational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Last update: 29 Oct 1996, 17:08:31 PST.