Computing shortest transversals of sets (extended abstract)
Binay Kumar Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenović, Godfried Toussaint, Jorge Urrutia · 1991
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 and of a family of n line segments.We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices.In general, finding a line transversal for a family of n objects takes fl(n log n) time.This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.