Description
An algorithm is presented for determining in O(n lg n) time whether there exists a line that stabs each of n polygons whose edges are from three sets of parallel lines. Using this algorithm, one can determine in O(n lg n) time whether there exists a line that stabs each of n isothetic boxes or rectangles. If any stabbing line exists, the algorithm computes and returns one such stabbing line.