## 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