Math @ Duke
|
Publications [#235451] of Pankaj K. Agarwal
Papers Published
- 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
(January, 2003),
pp. 7-18, ISSN 0302-9743 [doi]
(last updated on 2023/06/02)
Abstract: 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.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|