I/O-efficient structures for orthogonal range-max and stabbing-max queries
Published
Journal Article
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.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Arge, L; Yang, J; Yi, K
Published Date
- January 1, 2003
Published In
Volume / Issue
- 2832 /
Start / End Page
- 7 - 18
Electronic International Standard Serial Number (EISSN)
- 1611-3349
International Standard Serial Number (ISSN)
- 0302-9743
Digital Object Identifier (DOI)
- 10.1007/978-3-540-39658-1_4
Citation Source
- Scopus