Math @ Duke

Publications [#235607] of Pankaj K. Agarwal
Papers Submitted
 Agarwal, PK; Berg, MD; Gudmundsson, J; Hammar, M; Haverkort, HJ, Boxtrees and Rtrees with nearoptimal query time,
Discrete & Computational Geometry, vol. 28 no. 3
(2002),
pp. 291312, ISSN 01795376 [doi]
(last updated on 2018/09/20)
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

