Stabbing parallel segments with a convex polygon
Michael T. Goodrich, Jack Scott Snoeyink · Computer Vision Graphics and Image Processing · 1990
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.