I/O-efficient structures for orthogonal range-max and stabbing-max queries


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