Pseudotriangle

Although the words "pseudotriangle" and "pseudotriangulation" have been used with various meanings in mathematics for much longer,[1] the terms as used here were introduced in 1993 by Michel Pocchiola and Gert Vegter in connection with the computation of visibility relations and bitangents among convex obstacles in the plane.

Pointed pseudotriangulations were first considered by Ileana Streinu (2000, 2005) as part of her solution to the carpenter's ruler problem, a proof that any simple polygonal path in the plane can be straightened out by a sequence of continuous motions.

Pseudotriangulations have also been used for collision detection among moving objects[2] and for dynamic graph drawing and shape morphing.

Pocchiola and Vegter (1996a, 1996b, 1996c) originally defined a pseudotriangle to be a simply-connected region of the plane bounded by three smooth convex curves that are tangent at their endpoints.

[7] However, subsequent work has settled on a broader definition that applies more generally to polygons as well as to regions bounded by smooth curves, and that allows nonzero angles at the three vertices.

In this broader definition, a pseudotriangle is a simply-connected region of the plane, having three convex vertices.

The curves along the pseudotriangle boundary between each pair of convex vertices either lie within the triangle or coincide with one of its edges.

It is not hard to see that a pointed pseudotriangulation is a pseudotriangulation of its convex hull: all convex hull edges may be added while preserving the angle-spanning property, and all interior faces must be pseudotriangles else a bitangent line segment could be added between two vertices of the face.

The same argument also shows that f = v − 1 (including the convex hull as one of the faces), so the pseudotriangulation must have exactly v − 2 pseudotriangles.