Pitteway triangulation

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
.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Triangulation de delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • Triangulation de Pitteway — À gauche: Une triangulation de Pitteway. Chaque arrête de la triangulation de Delaunay, en noir, coupe son dual associé dans le diagramme de Voronoi, en pointillé bleu. À droite : une triangulation de Delaunay qui n est pas une triangulation …   Wikipédia en Français

  • Triangulation de Delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits en gris. En mathématiques et plus particulièrement en …   Wikipédia en Français

  • Delaunay triangulation — A Delaunay triangulation in the plane with circumcircles shown In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of… …   Wikipedia

  • Delaunay triangulation — Triangulation de Delaunay Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Triangle (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Triangle (homonymie) », sur le Wiktionnaire (dictionnaire universel) Le mot « triangle », du …   Wikipédia en Français

Share the article and excerpts

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