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 minimum set of spanning line segments for an arbitrary polyhedron P. When the number 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 for a convex polyhedron, hence is optimal in this case; its time complexity Θ (m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron.
展开▼
