Michael E. Hohmeyer and Seth J. Teller

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-91-634

, 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-634.pdf

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.

---

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},
    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