Computing shortest transversals

We present an O(nlog²n) time and O(n) space algorithm for computing the shortest line segment that intersects a set of n given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run in O(nlog n) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set of n isothetic rectangles in the plane in O(nlog k) time, where k is the combinatorial complexity of the space of transversals and k≤4 n. These results find application in: (1) line-fitting between a set of n data ranges where it is desired to obtain the shortest line-of-fit, (2) finding the shortest line segment from which a convex n-vertex polygon is weakly externally visible, and (3) determing the shortest line-of-sight between two edges of a simple n-vertex polygon, for which O(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.