Affordable Access

Publisher Website

Sparse dominance queries for many points in optimal time and space

Information Processing Letters
Publication Date
DOI: 10.1016/s0020-0190(97)00181-6
  • Dominating Point
  • Interval Tree
  • Priority Search Tree
  • Layered Witness Graph
  • Computer Science
  • Mathematics


Abstract A point p ϵ R 2 dominates a point q ϵ R 2 if p. x ⩾ q. x and p. y ⩾ q. y. Given is a set S of n different points, a sequence Q of k query points chosen from S, and a function ƒ: N → N, ƒ(x) ⩽ x. In the Sparse Dominance Query Problem ( SDQP) we have to compute for each q ϵ Q the set D( q) of points in S ⧹ { q} that dominate q if q is ƒ- sparse and otherwise a close subset D′( q) of D( q) with ¦ D′(q)¦ = ƒ(n). We prove that Ω (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 O( n log n + K( S, Q)) time using O( n) space for any function ƒ and for any value of k. We also show that the LWG can be modified such that points p ϵ R 2 can be dynamically inserted into and deleted from S in O(¦ D ̃ (p)¦ log n) time, where D ̃ (p) denotes the set of points in S ⧹ { p} that are dominated by p.

There are no comments yet on this publication. Be the first to share your thoughts.