Triangulation is the division of a surface into a set of Triangles, usually with the restriction that each Triangle side is entirely shared by two adjacent Triangles. It was proved in 1930 that every surface has a triangulation, but it might require an infinite number of Triangles. A surface with a finite number of triangles in its triangulation is called Compact. B. Chazelle showed that an arbitrary Simple Polygon can be triangulated in linear time.

© 1996-9

1999-05-26