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