Staying in the middle: exact and approximate medians in R1 and R2 for moving points

Pankaj K. Agarwal, Mark de Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-Peled

Research output: Contribution to conferencePaperAcademic

12 Citations (Scopus)
2 Downloads (Pure)

Abstract

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 fun- damental 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.
Original languageEnglish
Pages43-46
Number of pages4
Publication statusPublished - 1 Jan 2005
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: 10 Aug 200512 Aug 2005

Conference

Conference17th Canadian Conference on Computational Geometry, CCCG 2005
Country/TerritoryCanada
CityWindsor
Period10/08/0512/08/05

Fingerprint

Dive into the research topics of 'Staying in the middle: exact and approximate medians in R1 and R2 for moving points'. Together they form a unique fingerprint.

Cite this