computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, 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 Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...

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 In mathematics and computational geometry, the Gabriel graph of a set S of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph G with vertex set S in which any two distinct po ...

and

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

History

The concept of a Pitteway triangulation was introduced by . See also , 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 .

Counterexamples

points out that not every point set supports a Pitteway triangulation. For instance, any triangulation of a regular pentagon includes a central

isosceles triangle In geometry, an isosceles triangle () is a triangle that has two sides of equal length. Sometimes it is specified as having ''exactly'' two sides of equal length, and sometimes as having ''at least'' two sides of equal length, the latter versio ...

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

together with the

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

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.; .

Notes

References

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