Minimum Polygon Transversals of Line Segments

Let $ be used to denote a finite set of planar geometric objects. Define a polygon transversal of $ as a closed simple polygon that simultaneously intersects every object in $, and a minimum polygon transversal of $ as a polygon transversal of $ with minimum perimeter. If $ is a set of points then the minimum polygon transversal of $ is the convex hull of $. However, when the objects in $ have some dimension then the minimum polygon transversal and the convex hull may no longer coincide. We consider the case where $ 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 d- log n). The general problem for line segments is not known to be polynomial nor is it known to be NP-hard