Michael E. Hohmeyer and Seth J. Teller
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-634
June 1991
http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-634.pdf
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.
BibTeX citation:
@techreport{Hohmeyer:CSD-91-634, Author = {Hohmeyer, Michael E. and Teller, Seth J.}, Title = {Stabbing Isothetic Boxes and Rectangles in O(n lg n) Time}, Institution = {EECS Department, University of California, Berkeley}, Year = {1991}, Month = {Jun}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/5529.html}, Number = {UCB/CSD-91-634}, Abstract = {An algorithm is presented for determining in O(<i>n</i> lg <i>n</i>) time whether there exists a line that stabs each of <i>n</i> polygons whose edges are from three sets of parallel lines. Using this algorithm, one can determine in O(<i>n</i> lg <i>n</i>) time whether there exists a line that stabs each of <i>n</i> isothetic boxes or rectangles. If any stabbing line exists, the algorithm computes and returns one such stabbing line.} }
EndNote citation:
%0 Report %A Hohmeyer, Michael E. %A Teller, Seth J. %T Stabbing Isothetic Boxes and Rectangles in O(n lg n) Time %I EECS Department, University of California, Berkeley %D 1991 %@ UCB/CSD-91-634 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/5529.html %F Hohmeyer:CSD-91-634