Triangulation is the division of a surface or plane polygon into a set of triangles, usually with the restriction that each triangle side
is entirely shared by two adjacent triangles. It was
proved in 1925 that every surface has a triangulation, but it might require an infinite
number of triangles and the proof is difficult (Francis
and Weeks 1999). A surface with a finite number of triangles in its triangulation
is called compact.
Wickham-Jones (1994) gives an algorithm for triangulation ("otectomy"), and
O'Rourke (1998, p. 47) sketches a method for improving this to , as first done by Lennes (1911). Garey et al. (1978)
gave an algorithmically straightforward method for triangulation, which was for many years believed
optimal. However, Tarjan and van Wyk (1988) produced an algorithm. This was followed by an unexpected result
due to Chazelle (1991), who showed that an arbitrary simple
polygon can be triangulated in . However, according to Skiena (1997), "this algorithm
is quite hopeless to implement."
Amato, N. M.; Goodrich, M. T.; and Ramos, E. A. "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time."
Discr. Comput. Geom.26, 245-265, 2001.Chazelle, B. "Triangulating
a Simple Polygon in Linear Time." Disc. Comput. Geom.6, 485-524,
1991.de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O.
"Polygon Triangulation: Guarding an Art Gallery." Ch. 3 in Computational
Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag,
pp. 45-61, 2000.Eppstein, D. "Triangles and Simplices."
http://www.ics.uci.edu/~eppstein/junkyard/triangulation.html.Fournier,
A. and Montuno, D. Y. "Triangulating Simple Polygons and Equivalent Problems."
ACM Trans. Graphics3, 153-174, 1984.Francis, G. K.
and Weeks, J. R. "Conway's ZIP Proof." Amer. Math. Monthly106,
393-399, 1999.Friedman, E. "Triangulating Triangles." http://www.stetson.edu/~efriedma/triang/.Garey,
M. R.; Johnson, D. S.; Preparata, F. P.; and Tarjan, R. E. "Triangulating
a Simple Polygon." Inform. Process. Lett.7, 175-179, 1978. Kraus, M. "Polygon Triangulation." http://library.wolfram.com/infocenter/MathSource/23/.Lennes,
N. J. "Theorems on the Simple Finite Polygon and Polyhedron." Amer.
J. Math.33, 37-62, 1911.O'Rourke, J. §2.3 in Computational
Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.Radó,
T. "Über den Begriff der Riemannschen Fläche." Acta Litt.
Sci. Reg. Univ. Hungar. Francisco-Josephinae2, 101-121, 1924-1926.Skiena,
S. S. "Triangulation." §8.6.3 in The
Algorithm Design Manual. New York: Springer-Verlag, pp. 355-357, 1997.Tarjan,
R. and van Wyk, C. "An Algorithm for Triangulating a Simple Polygon."
SIAM J. Computing17, 143-178, 1988. Wickham-Jones, T. "ExtendGraphics
Packages." http://library.wolfram.com/infocenter/Books/3753/.Wickham-Jones,
T. Mathematica
Graphics: Techniques and Applications. New York: Springer-Verlag, pp. 406
and 448, 1994.
algorithm for triangulation ("otectomy"), and
O'Rourke (1998, p. 47) sketches a method for improving this to 
, as first done by Lennes (1911). Garey et al. (1978)
gave an algorithmically straightforward 
method for triangulation, which was for many years believed
optimal. However, Tarjan and van Wyk (1988) produced an 
algorithm. This was followed by an unexpected result
due to Chazelle (1991), who showed that an arbitrary simple
polygon can be triangulated in 
. However, according to Skiena (1997), "this algorithm
is quite hopeless to implement."
Kraus, M. "Polygon Triangulation." 
Algorithm for Triangulating a Simple Polygon."
SIAM J. Computing 17, 143-178, 1988.