2002-57: Lower bounds for the size of binary space partition of rectangles

DIMACS TR: 2002-57

Lower bounds for the size of binary space partition of rectangles

Authors: Ying Liu

ABSTRACT
Binary space partition (BSP) tree is one of the most popular data structures in computational geometry. We proved that the lower bound on the exact size of BSP trees for a set of $n$ isothetic rectangles in the plane is $2n-o(n)$ when the rectangles tile the underlying space, this closed the gap between the upper and lower bounds for this case. Also, in general, for a set of $n$ isothetic rectangles in the plane, we improved the lower bound from $\frac{9}{4}n-o(n)$ to $\frac{7}{3}n-o(n)$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-57.ps.gz

DIMACS Home Page