TOPICS
Search

Triangulation

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Triangulation

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 O(n^3) algorithm for triangulation ("otectomy"), and O'Rourke (1998, p. 47) sketches a method for improving this to O(n^2), as first done by Lennes (1911). Garey et al. (1978) gave an algorithmically straightforward O(nlnn) method for triangulation, which was for many years believed optimal. However, Tarjan and van Wyk (1988) produced an O(nlglgn) algorithm. This was followed by an unexpected result due to Chazelle (1991), who showed that an arbitrary simple polygon can be triangulated in O(n). However, according to Skiena (1997), "this algorithm is quite hopeless to implement."

See also

Art Gallery Theorem, Circumcenter of Mass, Compact Surface, Delaunay Triangulation, Japanese Theorem, Mesh, Simple Polygon, Tessellation, Triangle Mesh, Triangulation Point

Explore with Wolfram|Alpha

References

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." https://ics.uci.edu/~eppstein/junkyard/triangulation.html.Fournier, A. and Montuno, D. Y. "Triangulating Simple Polygons and Equivalent Problems." ACM Trans. Graphics 3, 153-174, 1984.Francis, G. K. and Weeks, J. R. "Conway's ZIP Proof." Amer. Math. Monthly 106, 393-399, 1999.Friedman, E. "Problem of the Month (December 2006)." https://erich-friedman.github.io/mathmagic/1206.html.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." https://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-Josephinae 2, 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 O(nlglgn) Algorithm for Triangulating a Simple Polygon." SIAM J. Computing 17, 143-178, 1988.Wickham-Jones, T. Mathematica Graphics: Techniques and Applications. New York: Springer-Verlag, pp. 406 and 448, 1994. Wickham-Jones, T. "ExtendGraphics Packages." https://library.wolfram.com/infocenter/Books/3753/.

Referenced on Wolfram|Alpha

Triangulation

Cite this as:

Weisstein, Eric W. "Triangulation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Triangulation.html

Subject classifications