Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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},
    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://www.eecs.berkeley.edu/Pubs/TechRpts/1991/5529.html
%F Hohmeyer:CSD-91-634