Exact size of binary space partitionings and improved rectangle tiling algorithms

被引：14

作者：

Berman, P ^{[1
]}

Dasgupta, B

Muthukrishnan, S

机构：

[1] Penn State Univ, Dept Comp Sci, University Pk, PA 16802 USA

[2] Univ Illinois, Dept Comp Sci, Chicago, IL 60607 USA

[3] AT&T Labs Res, Florham Pk, NJ 07932 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2002年 / 15卷 / 02期

关键词：

binary space partitions; exact bounds; tiling; approximation algorithms;

D O I：

10.1137/S0895480101384347

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 3 n 1 in general, and an upper bound of 2n - 1 if the rectangles tile the underlying space. This improves the upper bounds of 4 n in [ V. Hai Nguyen and P. Widmayer, 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 rectangles 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.

引用

页码：252 / 267

页数：16