Point set triangulation

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.

Sometimes it is desirable to have a triangulation with special properties, e.g., in which the triangles each have large angles ("splinter" triangles are avoided).

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.

Triangulation of the set of points may be a subproblem of the convex hull question in the space of dimension larger by 1.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Triangulation (disambiguation) — Triangulation refers to measurement by using triangles. The term triangulation may also refer to:Mathematics and computer science*Subdivisions of spaces into triangles or higher dimensional simplices: **triangulation (advanced geometry), division …   Wikipedia

  • Triangulation d'un ensemble de points — Une triangulation d un ensemble de points P dans le plan est une triangulation de l’enveloppe convexe de P, tous les points de P formant alors des sommets de cette triangulation. Les triangulations sont un sous ensemble de graphes planaires… …   Wikipédia en Français

  • Pitteway triangulation — In computational geometry, a Pitteway triangulation is a point set triangulation in which the nearest neighbor of any point p within the triangulation is one of the vertices of the triangle containing p .Alternatively, it is a Delaunay… …   Wikipedia

  • Minimum-weight triangulation — In computational geometry and computer science, the minimum weight triangulation (MWT) problem is the problem of finding a triangulation of minimal weight. Of particular interest is the problem of finding a minimum weight point set triangulation …   Wikipedia

  • Triangulation — In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly. The point can… …   Wikipedia

  • Triangulation (computer vision) — In computer vision triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to solve this problem it is necessary to know the parameters of the camera projection function… …   Wikipedia

  • Triangulation station — A trigonometrical station, triangulation pillar or trig point is a fixed surveying station for the geodetic surveying and other surveying projects on nearby areas. They are generally known as Trigonometrical stations in North America and trig… …   Wikipedia

  • Point location — The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided… …   Wikipedia

  • Triangulation (topology) — In mathematics, topology generalizes the notion of triangulation in a natural way as follows: A triangulation of a topological space X is a simplicial complex K , homeomorphic to X , together with a homeomorphism h : K o X . Triangulation is… …   Wikipedia

  • Point cloud — A point cloud is a set of vertices in a three dimensional coordinate system. These vertices are usually defined by X , Y and Z coordinates.Point clouds are most often created by 3D scanners. These devices measure a large number of points on the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”