The Library
Optimal binary space partitions for orthogonal objects
Tools
Tools
Tools
Paterson, Michael S. and Yao, F. Frances (1990) Optimal binary space partitions for orthogonal objects. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-158.pdf - Requires a PDF viewer. Download (12Mb) | Preview |
Abstract
A binary space partition, or BSP is a scheme for recursively dividing a configuration of objects by hyperplanes until all objects are separated. BSPs are widely used in computer graphics as the underlying data structure for computations such as real-time hidden-surface removal, ray tracing, and solid modelling. In these applications, the computational cost is directly related to the size of the BSP, ie the toal number of fragments of the objects generated by the partition. Until recently, the question of minimizing the size of BSPs for given inputs had been studied only empirically. We concentrate here on ortogonal objects, a case which arises frequently in practice and deserves special attention. We construct BSPs of linear size for any set of orthogonal line segments in the plane. In three dimensions, BSPs of size O(n<sup>1.5</sup>) for any set of n mutually orthogonal line segments or rectangles are constructed. These bounds are optimal and may be contrasted with the omega(n<sup>2</sup>) bound for general polygonal objects in R<sup>3</sup>.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computer graphics | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | April 1990 | ||||
| Dates: |
|
||||
| Number: | Number 158 | ||||
| Number of Pages: | 13 | ||||
| DOI: | CS-RR-158 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | M.S. Paterson and F.F. Yao, “Optimal Binary Space Partitions for Orthogonal Objects”, <i>Journal of Algorithms</i> <b>13</b>, pp. 99-113 (1992) | ||||
| Funder: | Science and Engineering Research Council (Great Britain) (SERC) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
