A triangulation of a polygon P is its partition into non-overlapping triangles whose union is P. In the strictest sense, these triangles may have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serve as vertices of triangles.
A convex polygon is trivial to triangulate in linear time, by adding edges from one vertex to all other vertices. In fact, Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time.
It is not surprising that triangulations of the plane would be of considerable interest because among all graphs that can be drawn in the plane with a fixed number of vertices, these graphs have the maximal number of edges.
Triangulations are also known as maximal planar graphs because of the property that if one adds even a single edge between two vertices of a triangulation that are not already joined, the result is a graph which can not be redrawn in the plane without crossings at points that are not vertices.
triangulations, near triangulations, triangulatedpolygons) so that they can see what properties all the structures have and what properties fail to hold due to the small changes in the definitions of the structures.
Feeds |
Contact