On Stable Line Segments in Triangulations
Andranik Mirzaian, Cao An Wang, Yinfeng Xu · 1996
Let S be a set of n points in the plane and E denote the set of all the line segments with endpoints in S. A line segment pq with p; q 2 S is called a stable line segment of all triangulations of S, if no line segment in E properly intersects pq. The intersection of all possible triangulations of S then is the set of all stable line segments in S, denoted by SL(S). As a combinatorial problem, various properties of stable line segments of a set of planar points have been investigated in [13]. It is shown that the maximum number of stable line segments in S is 2(n 1). There is an interesting relationship between stable line segments and so-called extreme line segments EL(S) [6]. A line segment pq with p; qS is called an extreme line segment if fp; qg = E \\H for some open half-plane H [6]. Then, we have that CH(S) EL(S) SL(S): A more important property is the relationship between SL(S) and so-called k-optimal triangulations. Let T (S) denote a triangulation of S. T (S) is called a k-optimal triangu-1