Computing an almost minimum set of spanning line segments of a polyhedron

A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E-3 such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimu m set of spanning line segments for an arbitrary polyhedron P. When the num ber of extreme vertices of P is odd, the computed SLS is minimum; when the number of extreme vertices of P is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity f or a convex polyhedron, hence is optimal in this case; its time complexity is circle minus (m log m) for an arbitrary polyhedron, where m is the numbe r of vertices of the polyhedron.