$$\beta $$ β -skeletons for a Set of Line Segments in $$R^2 $$ R 2
\(\beta \)-skeletons are well-known neighborhood graphs for a set of points. We extend this notion to sets of line segments in the Euclidean plane and present algorithms computing such skeletons for the entire range of \(\beta \) values. The main reason of such extension is the possibility to study \(\beta \)-skeletons for points moving along given line segments. We show that relations between \(\beta \)-skeletons for \(\beta > 1\), 1-skeleton (Gabriel Graph), and the Delaunay triangulation for sets of points hold also for sets of segments. We present algorithms for computing circle-based and lune-based \(\beta \)-skeletons. We describe an algorithm that for \(\beta \ge 1\) computes the \(\beta \)-skeleton for a set S of n segments in the Euclidean plane in \(O(n^2 \alpha (n) \log n)\) time in the circle-based case and in \(O(n^2 \lambda _4(n))\) in the lune-based one, where the construction relies on the Delaunay triangulation for S, \(\alpha \) is a functional inverse of Ackermann function and \(\lambda _4(n)\) denotes the maximum possible length of a (n, 4) Davenport-Schinzel sequence. When \(0 < \beta < 1\), the \(\beta \)-skeleton can be constructed in a \(O(n^3 \lambda _4(n))\) time. In the special case of \(\beta = 1\), which is a generalization of Gabriel Graph, the construction can be carried out in a \(O(n \log n)\) time.