Stabbing parallel segments with a convex polygon

We present an algorithm that, given a set of n parallel line segments in the plane, finds a convex polygon whose boundary intersects each segment at least once or that determines that none exists. Our algorithm runs in O(nlogn) steps and linear space, which is optimal. Our solution involves a reduction to a bipartite stabbing problem, using a “point-sweeping” or “chain-unwrapping” technique. We use geometric duality to solve bipartite stabbing. We also indicate how to extend our algorithm to find the convex polygon with minimum area or perimeter that intersects each segment.