Binary Space Partitions for Fat Rectangles
Authors:
- Pankaj K. AgarwalPAPankaj K. Agarwal
- Edward F. GroveEGEdward F. Grove
- T. M. MuraliTMT. M. Murali
- Jeffrey Scott VitterJVJeffrey Scott Vitter
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (5) , 1422-1448
Abstract
We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in ${\Bbb R}^3$ such that the aspect ratio of each rectangle in S is at most $\alpha$, for some constant $\alpha \geq 1$. We present an $n2^{O(\sqrt{\log n})}$-time algorithm to build a binary space partition of size $n2^{O(\sqrt{\log n})}$ for S. We also show that if m of the n rectangles in S have aspect ratios greater than $\alpha$, we can construct a BSP of size $n\sqrt{m}2^{O(\sqrt{\log n})}$ for S in $n\sqrt{m}2^{O(\sqrt{\log n})}$ time. The constants of proportionality in the big-oh terms are linear in $\log \alpha$. We extend these results to cases in which the input contains nonorthogonal or intersecting objects.
Keywords
This publication has 16 references indexed in Scilit:
- Constructing Binary Space Partitions for Orthogonal Rectangles in Practice1998
- Linear size binary space partitions for fat objectsLecture Notes in Computer Science, 1995
- Approximation algorithms for geometric tour and network design problems (extended abstract)1995
- A SURVEY OF OBJECT-SPACE HIDDEN SURFACE REMOVALInternational Journal of Computational Geometry & Applications, 1994
- Optimal binary space partitions for orthogonal objectsJournal of Algorithms, 1992
- Fast object-precision shadow generation for area light source1992
- Efficient binary space partitions for hidden-surface removal and solid modelingDiscrete & Computational Geometry, 1990
- Set operations on polyhedra using binary space partitioning treesACM SIGGRAPH Computer Graphics, 1987
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal AlgorithmSIAM Journal on Computing, 1984
- A Characterization of Ten Hidden-Surface AlgorithmsACM Computing Surveys, 1974