Line transversal algorithms in the plane
Peter Egyed · eScholarship@McGill (McGill) · 1992
Consider the following fundamental geometric problem: given a family of convex sets in the plane, does there exist a line that intersects every member of the family? Such a line is known as a line transversal for the family. The problem has been considered for many different families of objects. In general, $ Omega(n log n)$ time is required to compute a line transversal of a family of n objects. In this thesis, it is shown that several line transversal problems can be solved in $O(n)$ time. The problem of computing a shortest line segment that intersects every member of a family of objects is also considered. In particular, $O(n log n)$ time algorithms are proposed for computing a shortest transversal of a family of n lines and of a family of n line segments. As well, an $O(n log sp2 n)$ time algorithm for computing a shortest transversal of a family of convex polygons with a total of n vertices is presented. Our algorithm for the line segment version of the shortest transversal problem is optimal.