|
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,〔For "pseudo-triangle" see, e.g., . On page 196 this paper refers to a "pseudo-triangle condition" in functional approximation. For "pseudo-triangulation" see, e.g., .〕 the terms as used here were introduced in 1993 by Pocchiola and Vegter in connection with the computation of visibility relations and bitangents among convex obstacles in the plane. Pointed pseudotriangulations were first considered by 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〔Agarwal et al. (2002).〕 and for dynamic graph drawing and shape morphing.〔Streinu (2006).〕 Pointed pseudotriangulations arise in rigidity theory as examples of minimally rigid planar graphs,〔Haas et al. (2005)〕 and in methods for placing guards in connection with the art gallery theorem.〔Speckmann and Tóth (2005).〕 The shelling antimatroid of a planar point set gives rise to pointed pseudotriangulations,〔Har-Peled (2002).〕 although not all pointed pseudotriangulations can arise in this way. For a detailed survey of much of the material discussed here, see Rote et al. (2006). == Pseudotriangles == Pocchiola and Vegter (1996a,b,c) 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. 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 three boundary curves connecting these three vertices must be convex, in the sense that any line segment connecting two points on the same boundary curve must lie entirely outside or on the boundary of the pseudotriangle. Thus, the pseudotriangle is the region between the convex hulls of these three curves, and more generally any three mutually tangent convex sets form a pseudotriangle that lies between them. For algorithmic applications it is of particular interest to characterize pseudotriangles that are polygons. In a polygon, a vertex is ''convex'' if it spans an interior angle of less than π, and ''concave'' otherwise (in particular, we consider an angle of exactly π to be concave). Any polygon must have at least three convex angles, because the total exterior angle of a polygon is 2π, the convex angles contribute less than π each to this total, and the concave angles contribute zero or negative amounts. A polygonal pseudotriangle is a polygon that has exactly three convex vertices. In particular, any triangle, and any nonconvex quadrilateral, is a pseudotriangle. The convex hull of any pseudotriangle is a triangle. The curves along the pseudotriangle boundary between each pair of convex vertices either lie within the triangle or coincide with one of its edges. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pseudotriangle」の詳細全文を読む スポンサード リンク
|