Stabbing Isothetic Boxes and Rectangles in O(n lg n) Time
Michael E. Hohmeyer and Seth J. Teller
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-634
June 1991
http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1991/5529.html},
Number = {UCB/CSD-91-634}
}
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://www.eecs.berkeley.edu/Pubs/TechRpts/1991/5529.html %F Hohmeyer:CSD-91-634