EXACT SIZE OF BINARY SPACE PARTITIONINGS AND IMPROVED RECTANGLE TILING ALGORITHMS

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: • An upper bound of 3n − 1 in general, and an upper bound of 2n − 1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P