DIMACS TR: 2000-26
On the Exact Size of the Binary Space Partitioning of Sets of Isothetic Rectangles with Applications
Authors: Piotr Berman, Bhaskar DasGupta and S. Muthukrishnan
We show an upper bound of 3n on size of the
Binary Space Partitioning (BSP) tree
for a set of n isothetic rectangles, and an upper bound of 2n
if the rectangles tile the underlying space. This improves
the previous bounds of 4n.
The BSP tree is one of the most popular data structures and
even ``small'' factor improvements of 4/3 or 2 we show
improves the performance of applications relying on the BSP tree.
Furthermore, our upper bounds yield improved approximation
algorithms for several rectangular tiling problems in the
literature. We also a show a lower bound of 2n in the worst
case for a BSP for n isothetic rectangles, and a lower bound of
1.5n if they must form a tiling of the space.
Paper Available at:
DIMACS Home Page