Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235607] of Pankaj K. Agarwal

Papers Submitted

  1. Agarwal, PK; Berg, MD; Gudmundsson, J; Hammar, M; Haverkort, HJ, Box-trees and R-trees with near-optimal query time, Discrete & Computational Geometry, vol. 28 no. 3 (2002), pp. 291-312, ISSN 0179-5376 [doi]
    (last updated on 2018/12/11)

    A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320