On Top-k Range Reporting in 2D Space
Saladi Rahul, Yufei Tao · 2015
Orthogonal range reporting (ORR) is a classic problem in computational geometry and databases, where the objective is to preprocess a set P of points in R2 such that, given an axis-parallel rectangle q, all the points in P ∩ Q can be reported efficiently. This paper studies a natural variant of the problem called top-k ORR, where each point p ∈ P carries a weight w(p) ∈R;. Besides q, a query also specifies an integer k ∈ [1, |P|], and needs to report the k points in q ∩ P with the largest weights. We present optimal or near-optimal structures for solving the top-k ORR problem in the pointer machine and external memory models. As a side product, our structures give new space-query tradeoff for the orthogonal range max problem, which is a special case of top-k ORR with k = 1.