Pitteway triangulation

Left: A Pitteway triangulation. Every interior Delaunay edge (black) crosses the corresponding dual Voronoi edge (dashed blue), although the convex hull edges do not cross their duals. Right: A Delaunay triangulation that is not a Pitteway triangulation; the red interior Delaunay edge does not cross the corresponding red dashed Voronoi edge, and some points in the top triangle have the bottom vertex as their nearest neighbor.

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 triangulation in which each internal edge crosses its dual Voronoi diagram edge. Pitteway triangulations are named after Michael Pitteway, who studied them in 1973. Not every point set supports a Pitteway triangulation. When such a triangulation exists it is a special case of the Delaunay triangulation, and consists of the union of the Gabriel graph and convex hull.

History

The concept of a Pitteway triangulation was introduced by Pitteway (1973). See also McLain (1976), who writes "An optimal partition is one in which, for any point within any triangle, that point lies at least as close to one of the vertices of that triangle as to any other data point." The name "Pitteway triangulation" was given by Okabe et al. (2000).

Counterexamples

Gold (1978) points out that not every point set supports a Pitteway triangulation. For instance, any triangulation of a regular pentagon includes a central isosceles triangle such that a point p near the midpoint of one of the triangle sides has its nearest neighbor outside the triangle.

Relation to other geometric graphs

When a Pitteway triangulation exists, the midpoint of each edge interior to the triangulation must have the two edge endpoints as its nearest neighbors, for any other neighbor would violate the Pitteway property for nearby points in one of the two adjacent triangles. Thus, a circle having that edge as diameter must be empty of vertices, so the Pitteway triangulation consists of the Gabriel graph together with the convex hull of the point set. Conversely, when the Gabriel graph and convex hull together form a triangulation, it is a Pitteway triangulation.

Since all Gabriel graph and convex hull edges are part of the Delaunay triangulation, a Pitteway triangulation, when it exists, is unique for points in general position and coincides with the Delaunay triangulation. However point sets with no Pitteway triangulation will still have a Delaunay triangulation.

In the Pitteway triangulation, each edge pq either belongs to the convex hull or crosses the edge of the Voronoi diagram that separates the cells containing p and q. In some references this property is used to define a Pitteway triangulation, as a Delaunay triangulation in which all internal Delaunay edges cross their dual Voronoi edges. However, a Pitteway triangulation may include convex hull edges that do not cross their duals.

References

• Dobrin, Adam (2005), A Review of Properties and Variations of Voronoi Diagrams (PDF), Whitman College

• Gold, C. M. (1978), "The practical generation and use of geographic triangular element data structures" (PDF), in Dutton, G. (ed.), Proceedings First International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems. Harvard Papers on Geographic Information Systems, vol. 5 — Data Structures: Surficial and Multi Dimensional., Boston: Laboratory for Computer Graphics and Spatial Analysis, Harvard University, pp. 1–18.

• McLain, D. H. (1976), "Two dimensional interpolation from random data.", The Computer Journal, 19 (2): 178–181, doi:10.1093/comjnl/19.2.178.

• Okabe, Atsuyuki; Boots, Barry N.; Chiu, Sung Nok; Sugihara, Kokichi (2000), Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley.

• Pitteway, M. L. V. (1973), "Computer graphics research in an academic environment", Datafair '73.