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 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 harvtxt|Pitteway|1973. See also harvtxt|McLain|1976, who writes "An optimal partitionis one in which, for any point within any triangle, that point lies at leastas close to one of the vertices of that triangle as to any other data point." The name "Pitteway triangulation" was given by harvtxt|Okabe|Boots|Chiu|Sugihara|2000.

Counterexamples

harvtxt|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. [harvtxt|Okabe|Boots|Chiu|Sugihara|2000; harvtxt|Dobrin|2005.]

Notes

References

*citation
first = Adam
last = Dobrin
title = A Review of Properties and Variations of Voronoi Diagrams
year = 2005
publisher = Whitman College
url = http://www.whitman.edu/mathematics/SeniorProjectArchive/2005/dobrinat.pdf
*citation
first = C. M.
last = Gold
contribution = The practical generation and use of geographic triangular element data structures
editor-first = G.
editor-last = Dutton
title = 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.
publisher = Laboratory for Computer Graphics and Spatial Analysis, Harvard University
location = Boston
year = 1978
pages = 1–18
contribution-url = http://www.voronoi.com/pdfs/1970s/The_practical_generation_and_use.pdf.
*citation
last = McLain
first = D. H.
year = 1976
title = Two dimensional interpolation from random data.
journal = The Computer Journal
volume = 19
pages = 178–181.

*citation
title = Spatial Tessellations: Concepts and Applications of Voronoi Diagrams
first1 = Atsuyuki
last1 = Okabe
first2 = Barry N.
last2 = Boots
first3 = Sung Nok
last3 = Chiu
first4 = Kokichi
last4 = Sugihara
publisher = Wiley
year = 2000.

*citation
last = Pitteway
first = M. L. V.
contribution = Computer graphics research in an academic environment
title = Datafair '73
year = 1973.