Lesson plan

Point-set triangulation

A triangulation of a set of points \mathcal{P} in the Euclidean space \mathbb{R}^d is a simplicial complex that covers the convex hull of \mathcal{P} , and whose vertices belong to \mathcal{P} . In the plane (when \mathcal{P} is a set of points in \mathbb{R}^2 ), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of \mathcal{P} are vertices of its triangulations. In this case, a triangulation of a set of points \mathcal{P} in the plane can alternatively be defined as a maximal set of non-crossing edges between points of \mathcal{P} . In the plane, triangulations are special cases of planar straight-line graphs. The Delaunay triangulations are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points \mathcal{P} in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of \mathcal{P} . Triangulations have a number of applications, and there is an interest to find the "good" triangulations of a given point set under some criteria as, for instance minimum-weight triangulations. 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).…

Back to article

Article summary

A triangulation of a set of points \mathcal{P} in the Euclidean space \mathbb{R}^d is a simplicial complex that covers the convex hull of \mathcal{P} , and whose vertices belong to \mathcal{P} . In the plane (when \mathcal{P} is a set of points in \mathbb{R}^2 ), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of \mathcal{P} are vertices of its triangulations. In this case, a triangulation of a set of points \mathcal{P} in the plane can alternatively be defined as a maximal set of non-crossing edges between points of \mathcal{P} . In the plane, triangulations are special cases of planar straight-line graphs. The Delaunay triangulations are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points \mathcal{P} in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of \mathcal{P} . Triangulations have a number of applications, and there is an interest to find the "good" triangulations of a given point set under some criteria as, for instance minimum-weight triangulations. 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).…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.