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

Math @ Duke



Publications [#235451] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Arge, L; Yang, J; Yi, K, I/O-efficient structures for orthogonal range-max and stabbing-max queries, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2832 (2003), pp. 7-18, ISSN 0302-9743
    (last updated on 2018/12/13)

    We develop several linear or near-linear space and I/O-efficient dynamic data structures for orthogonal range-max queries and stabbing-max queries. Given a set of N weighted points in ℝd, the range-max problem asks for the maximum-weight point in a query hyperrectangle. In the dual stabbing-max problem, we are given N weighted hyper-rectangles, and we wish to find the maximum-weight rectangle containing a query point. Our structures improve on previous structures in several important ways. © Springer-Verlag 2003.
ph: 919.660.2800
fax: 919.660.2821

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