Indexing Reverse Top-k Queries in Two Dimensions

We consider the recently introduced monochromatic reverse top−k query which asks for, given a (possibly new) tuple q and a dataset \(\mathcal{D}\), all possible top−k queries on \(\mathcal{D}\cup\{q\}\) for which q is in the result. Towards this problem, we introduce the first query-agnostic approach, which leads to an efficient index. We present the novel insight that by representing the dataset as an arrangement of lines, a critical k-polygon can be identified and can singularly answer reverse top−k queries.