Max-count aggregation estimation for moving points

Many interesting problems regarding moving objects can be reduced to the following question: Given a set S of moving points on a line and two other movings points A and B on the same line, what is the maximum number of points in S that will be simultaneously between A and B within a time interval (t₁, t₂)? We propose an algorithm that can estimate the answer for arbitrary A and B and any fixed S in a chosen constant time. We show that the error rate of the estimation is related to this chosen constant and some other parameters of the input data. Our experimental results show that high accuracy estimation can be achieved when S has a large number of points and A and B are not too close to each other.