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 language | English |
|---|---|
| Pages | 43-46 |
| Number of pages | 4 |
| Publication status | Published - 1 Jan 2005 |
| Event | 17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada Duration: 10 Aug 2005 → 12 Aug 2005 |
Conference
| Conference | 17th Canadian Conference on Computational Geometry, CCCG 2005 |
|---|---|
| Country/Territory | Canada |
| City | Windsor |
| Period | 10/08/05 → 12/08/05 |
Funding
∗P.A. was partially supported by NSF under grants CCR-00-86013 EIA-98-70724, EIA-99-72879, EIA-01-31905, and CCR-02-04118, and by a grant from the U.S.-Israeli Binational Science Foundation. M.d.B. was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. Work by L.G. and J.G. was supported by NSF grant CCR-9910633 and grants from the Stanford Networking Research Center, the Okawa Foundation, and the Honda Corporation. S.H.-P. was supported by NSF CAREER award CCR-0132901.