Staying in the Middle: Exact and Approximate Medians in
R2 and R2 for Moving Points
Pankaj K. Agarwal,
Mark de Berg,
Jie Gao,
Leonidas J. Guibas,
and Sariel Har-Peled
Many divide-and-conquer based geometric algorithms and
order-statistics
problems ask for a point that lies ``in the middle'' of a given
point set. We study several fundamental problems of this type
for moving points in one and two dimensions. In particular, we
show how to kinetically maintain the median of a set of n
points moving on the real line, and a center point of a set of
n points moving in the plane, that is, a point such that
any line through it has at most 2n/3 on either side of
it. Since the maintenance of exact medians and center points
can be quite expensive, we also show how to maintain
µ-approximate
medians and center points and argue that the latter can be made
to be much more stable under motion. These results are based
on a new algorithm to maintain an µ-approximation
of a range space under insertions and deletions, which is of
independent interest. All our approximation algorithms run in
near-linear time.