Efficient algorithm for transversal of disjoint convex polygons. (Q1853055)

Given a set \(S\) of \(n\) disjoint convex polygons \({P_{i}\mid1<i<n}\) in a plane, each with \(k_{i}\) vertices, the transversal problem is to determine whether there exists a straight line that goes through every polygon in \(S.\) We show that the transversal problem can be solved in \(O(N+n\log n)\) time, where \(N=\sum_{i=1}^{n}k_{i}\) is the total number of vertices of the polygons.