### Abstract

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 | Canada |

City | Windsor |

Period | 10/08/05 → 12/08/05 |

### Fingerprint

### Cite this

*Staying in the middle: exact and approximate medians in R1 and R2 for moving points*. 43-46. Paper presented at 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada.

}

**Staying in the middle : exact and approximate medians in R1 and R2 for moving points.** / Agarwal, Pankaj K.; de Berg, Mark; Gao, Jie; Guibas, Leonidas J.; Har-Peled, Sariel.

Research output: Contribution to conference › Paper › Academic

TY - CONF

T1 - Staying in the middle

T2 - exact and approximate medians in R1 and R2 for moving points

AU - Agarwal, Pankaj K.

AU - de Berg, Mark

AU - Gao, Jie

AU - Guibas, Leonidas J.

AU - Har-Peled, Sariel

PY - 2005/1/1

Y1 - 2005/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85013021894&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85013021894

SP - 43

EP - 46

ER -