Acute Square Triangulation
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(n2) 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.