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

Published version (via Digital Object Identifier)

Duke Authors

Cited Authors

Agarwal, PK; Arge, L; Yang, J; Yi, K

Published Date

January 1, 2003

Published In

Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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

Scholars@Duke