Stabbing Orthogonal Objects in 3-Space

dc.contributor.authorMount, David M.en_US
dc.contributor.authorPu, Fan-Taoen_US
dc.date.accessioned2004-05-31T22:41:46Z
dc.date.available2004-05-31T22:41:46Z
dc.date.created1996-10en_US
dc.date.issued1998-10-15en_US
dc.description.abstractWe 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.extent668135 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/850
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3701en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-96-71en_US
dc.titleStabbing Orthogonal Objects in 3-Spaceen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3701.ps
Size:
652.48 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3701.pdf
Size:
221.26 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3701.ps