Efficient rectangle indexing algorithms based on point dominance

摘要

An approximate count of the number of (1) k-dimensional rectangles that contain, overlap or are within a query rectangle Q, and (2) linearly moving points that are to the left of a moving query point Q on the x-axis at time t, can be found in (poly)-logarithmic time in the number of rectangles or moving points.