Math @ Duke

Publications [#235399] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Grove, EF; Murali, TM; Vitter, JS, Binary space partitions for fat rectangles,
in Thirty Seventh Annual Symposium on Foundations of Computer Science,
Annual Symposium on Foundations of Computer Science  Proceedings
(1996),
pp. 482491
(last updated on 2018/08/15)
Abstract: We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, twodimensional rectangles in IR3 such that the aspect ratio of each rectangle in S is at most α, for some constant α≥1. We present an n2O(√log n)time algorithm to build a binary space partition of size n2O(√log n) for S. We also show that if m of the n rectangles in S have aspect ratios greater than α, we can construct a BSP of size n√m2O(√log n) for S in n√m2O(√log n) time. The constants of proportionality in the bigoh terms are linear in log α. We extend these results to cases in which the input contains nonorthogonal or intersecting objects.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

