TY - JOUR

T1 - Exact size of binary space partitionings and improved rectangle tiling algorithms

AU - Berman, Piotr

AU - Dasgupta, Bhaskar

AU - Muthukrishnan, S.

PY - 2002/2

Y1 - 2002/2

N2 - 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. Windmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255-259]. A BSP satisfying the upper bounds can be constructed in O(n log n) time. • A worst-case lower bound of 2n - o(n) in general, and 3n/2 - o(n) if the rectanles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of 4/3 or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees.

AB - 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. Windmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255-259]. A BSP satisfying the upper bounds can be constructed in O(n log n) time. • A worst-case lower bound of 2n - o(n) in general, and 3n/2 - o(n) if the rectanles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of 4/3 or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees.

KW - Approximation algorithms

KW - Binary space partitions

KW - Exact bounds

KW - Tiling

UR - http://www.scopus.com/inward/record.url?scp=0036487459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036487459&partnerID=8YFLogxK

U2 - 10.1137/S0895480101384347

DO - 10.1137/S0895480101384347

M3 - Article

AN - SCOPUS:0036487459

SN - 0895-4801

VL - 15

SP - 252

EP - 267

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -