# Stabbing Orthogonal Objects in 3-Space

 dc.contributor.author Mount, David M. en_US dc.contributor.author Pu, Fan-Tao en_US dc.date.accessioned 2004-05-31T22:41:46Z dc.date.available 2004-05-31T22:41:46Z dc.date.created 1996-10 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/850 dc.description.abstract We consider a problem that arises in the design of data structures for answering {\em visibility range queries}, that is, given a $3$-dimensional scene defined by a set of polygonal patches, we wish to preprocess the scene to answer queries involving the set of patches of the scene that are visible from a given range of points over a given range of viewing directions. These data structures recursively subdivide space into cells until some criterion is satisfied. One of the important problems that arise in the construction of such data structures is that of determining whether a cell represents a nonempty region of space, and more generally computing the size of a cell. In this paper we introduce a measure of the {\em size} of the subset of lines in 3-space that stab a given set of $n$ polygonal patches, based on the maximum angle and distance between any two lines in the set. Although the best known algorithm for computing this size measure runs in $O(n^2)$ time, we show that if the polygonal patches are orthogonal rectangles, then this measure can be approximated to within a constant factor in $O(n)$ time. (Also cross-referenced as UMIACS-TR-96-71) en_US dc.format.extent 668135 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3701 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-96-71 en_US dc.title Stabbing Orthogonal Objects in 3-Space en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿