Home Bookmarks Papers Blog

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.

Postscript, PDF.

Last modified: Tue Jul 19 20:48:46 CDT 2011