
P. K. Agarwal, M. de Berg, J. Gao, L. J. Guibas, and S. HarPeled, Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points, Proc. of the 17th Canadian Conference on Computational Geometry (CCCG’05), 4245, August, 2005.
Abstract:
Many divideandconquer based geometric algorithms and orderstatistics 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 epsilonapproximate 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 epsilonapproximation of a range space under insertions and deletions, which is of independent interest. All our approximation algorithms run in nearlinear time.
Bibtex:
@inproceedings{abgghsmeamRRmp05,
author="Pankaj K. Agarwal, Mark de Berg, Jie Gao, Leonidas J. Guibas, Sariel HarPeled",
title="Staying in the Middle: Exact and Approximate Medians in $R^1$ and $R^2$ for Moving Points",
booktitle="Proc. of the 17th Canadian Conference on Computational Geometry (CCCG・5)",
pages="4245",
month="August",
year="2005"
}

