2000-26: On the Exact Size of the Binary Space Partitioning of Sets of Isothetic Rectangles with Applications

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

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-26.ps.gz

DIMACS Home Page