Staying in the middle: exact and approximate medians in $R^1$ and $R^2$ for moving points

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

Staying in the middle: exact and approximate medians in $R^1$ and $R^2$ for moving points

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

14 Citations (Scopus)

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

Original language	English
Title of host publication	Proceedings 17th Canadian Conference on Computational Geometry (CCCG'05, Windsor, Ontario, Canada, August 10-12, 2005), Electronic proceedings
Pages	43-46
Number of pages	4
Publication status	Published - 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.

Cite this

@inproceedings{c7dd88ef5db54df89e417a5c3dab1cbe,

title = "Staying in the middle: exact and approximate medians in \$R\textasciicircum{}1\$ and \$R\textasciicircum{}2\$ for moving points",

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 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.",

author = "Agarwal, \{Pankaj K.\} and \{de Berg\}, Mark and Jie Gao and Guibas, \{Leonidas J.\} and Sariel Har-Peled",

year = "2005",

language = "English",

pages = "43--46",

booktitle = "Proceedings 17th Canadian Conference on Computational Geometry (CCCG'05, Windsor, Ontario, Canada, August 10-12, 2005), Electronic proceedings",

note = "17th Canadian Conference on Computational Geometry, CCCG 2005 ; Conference date: 10-08-2005 Through 12-08-2005",

}

Agarwal, PK, de Berg, M, Gao, J, Guibas, LJ & Har-Peled, S 2005, Staying in the middle: exact and approximate medians in $R^1$ and $R^2$ for moving points. in Proceedings 17th Canadian Conference on Computational Geometry (CCCG'05, Windsor, Ontario, Canada, August 10-12, 2005), Electronic proceedings. pp. 43-46, 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada, 10/08/05.

Staying in the middle: exact and approximate medians in $R^1$ and $R^2$ for moving points. / Agarwal, Pankaj K.; de Berg, Mark; Gao, Jie et al.
Proceedings 17th Canadian Conference on Computational Geometry (CCCG'05, Windsor, Ontario, Canada, August 10-12, 2005), Electronic proceedings. 2005. p. 43-46.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Staying in the middle

T2 - 17th Canadian Conference on Computational Geometry, CCCG 2005

AU - Agarwal, Pankaj K.

AU - de Berg, Mark

AU - Gao, Jie

AU - Guibas, Leonidas J.

AU - Har-Peled, Sariel

PY - 2005

Y1 - 2005

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

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

UR - https://www.scopus.com/pages/publications/85013021894

M3 - Conference contribution

SP - 43

EP - 46

BT - Proceedings 17th Canadian Conference on Computational Geometry (CCCG'05, Windsor, Ontario, Canada, August 10-12, 2005), Electronic proceedings

Y2 - 10 August 2005 through 12 August 2005

ER -

Staying in the middle: exact and approximate medians in $R^1$ and $R^2$ for moving points

Abstract

Conference

Funding

Other files and links

Fingerprint

Cite this