Math @ Duke

Publications [#235437] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Berg, MD; Gudmundsson, J; Hammar, M; Haverkort, HJ, Boxtrees and Rtrees with nearoptimal query time,
in Seventeenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(2001),
pp. 124133
(last updated on 2018/03/18)
Abstract: A boxtree is a boundingvolume hierarchy that uses axisaligned boxes as bounding volumes. The query complexity of a boxtree 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 boxtrees with small worstcase query complexity with respect to queries with axisparallel boxes and with points. We also prove lower bounds on the worstcase query complexity for boxtrees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert boxtrees to Rtrees, resulting in Rtrees with (almost) optimal query complexity.


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

