Binary space partitions for fat rectangles

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R³ such that the aspect ratio of each rectangle in S is at most α, for some constant a α⩾1. They present an n2^O(√logn)-time algorithm to build a binary space partition of size n2^O(√logn) for S. They also show that if m of the n rectangles in S have aspect ratios greater than α, they can contact a BSP of size n√m2^O(√logn) for S in n√2^O(√logn) time. The constants of proportionality in the big-oh terms are linear in log α. They extend these results to cases in which the input contains non-orthogonal or intersecting objects