Math @ Duke

Publications [#235586] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Murali, TM; Vitter, JS, Practical techniques for constructing Binary Space Partitions for orthogonal rectangles,
Proceedings of the Annual Symposium on Computational Geometry
(1997),
pp. 382384
(last updated on 2018/02/20)
Abstract: We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R3. We compare known algorithms with our implementation of a variant of a recent algorithm of Agarwal et al.. We show via an empirical study that their algorithm constructs BSPs of nearlinear size in practice and performs better than most of the other algorithms in the literature.


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

