Pseudotriangle

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

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.^[3] Pointed pseudotriangulations arise in rigidity theory as examples of minimally rigid planar graphs,^[4] and in methods for placing guards in connection with the art gallery theorem.^[5] The shelling antimatroid of a planar point set gives rise to pointed pseudotriangulations,^[6] although not all pointed pseudotriangulations can arise in this way.

For a detailed survey of much of the material discussed here, see Rote, Santos, and Streinu (2008).