| Vol. 15, No. 2, pp. 252–267 EXACT SIZE OF BINARY SPACE PARTITIONINGS AND IMPROVED RECTANGLE TILING ALGORITHMS ∗ (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| Abstract. 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. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||