COMPUTING SHORTEST TRANSVERSALS OF SETS

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family. In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family. In particular, we give O(n log n) time algorithms for computing a shortest transversal of a family of n lines, a family of n line segments, and a family of convex polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes Ω(n log n) time. This time bound holds for a family of n line segments as well as for a family of convex polygons with a total of n vertices. Hence, our shortest transversal algorithms for these families are optimal.