Point Set Triangulation
A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs.
There are special triangulations like the Delaunay triangulation which is the geometric dual of the Voronoi diagram. Subsets of the Delaunay triangulation are the Gabriel graph, nearest neighbor graph and the minimal spanning tree.
Triangulations have a number of applications, and there is an interest to find a "good" triangulation for a given point set under some criteria. One of them is a minimum-weight triangulation. Sometimes it is desirable to have a triangulation with special properties, e.g., in which all triangles have large angles (long and narrow ("splinter") triangles are avoided).
Given a set of edges that connect some pairs of the points, the problem to determine whether they contain a triangulation is NP-complete (Lloyd, 1977).
Read more about Point Set Triangulation: Triangulation and Convex Hull
Famous quotes containing the words point and/or set:
“Parents who want a fresh point of view on their furniture are advised to drop down on all fours and accompany the nine or ten month old on his rounds. It is probably many years since you last studied the underside of a dining room chair. The ten month old will study this marvel with as much concentration and reverence as a tourist in the Cathedral of Chartres.”
—Selma H. Fraiberg (20th century)
“This happy breed of men, this little world,
This precious stone set in the silver sea,
Which serves it in the office of a wall,
Or as a moat defensive to a house,
Against the envy of less happier lands,
This blessed plot, this earth, this realm, this England.”
—William Shakespeare (1564–1616)