Sparse dominance queries for many points in optimal time and space
✍ Scribed by T. Graf; V. Kamakoti
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 453 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
A point p E Iw* dominates a point 4 f JR' if p.x 3 q.x and p.y 2 q.y. Given is a set S of n different points, a sequence Q of k query points chosen from S, and a function f : IV + N, f(x) 6 x. In the Sparse Dominance Query Problem (SDQP) we have to compute for each q E Q the set D(q) of points in S \ {q} that dominate q if q is f-sparse and otherwise a close subset D'(q) of D(q) with 1 D'(q) 1 = f(n). We prove that fI( n log n + K( S, Q) ) is a lower time bound for the SDQP in the algebraic decision tree model of computation, where K( S, Q) is the total number of points reported. We present an algorithm based on the layered witness graph (LWG) that solves the SDQP in optimal 0( n log n + K( S, Q) ) time using O(n) space for any function f and for any value of k. We also show that the LWG can be modified such that points p E B* can be dynamically inserted into and deleted from S in 0( ID(p)I logn) time, where D(p) denotes the set of points in S \ {p} that are dominated by p. @ 1997 Elsevier Science B.V.