MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
David D. Rappaport · International Journal of Computational Geometry & Applications · 1995
Let S be used to denote a finite set of planar geometric objects. Define a polygon transversal of S as a closed simple polygon that simultaneously intersects every object in S, and a minimum polygon transversal of S as a polygon transversal of S with minimum perimeter. If S is a set of points then the minimum polygon transversal of S is the convex hull of S. However, when the objects in S have some dimension then the minimum polygon transversal and the convex hull may no longer coincide. We consider the case where S is a set of line segments. If the line segments are constrained to lie in a fixed number of orientations we show that a minimum polygon transversal can be found in O(n log n) time. More explicitely, if m denotes the number of line segment orientations, then the complexity of the algorithm is given by O(3mn+log n). The general problem for line segments is not known to be polynomial nor is it known to be NP-hard.