# 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