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

11 Citations (Scopus)

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.

Conference

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

Fingerprint

Approximation algorithms
Statistics
Geometric Algorithms
Divide and conquer
Order Statistics
Real Line
Point Sets
One Dimension
Deletion
Insertion
Linear Time
Approximation Algorithms
Two Dimensions
Maintenance
Motion
Line
Approximation
Range of data

Cite this

Agarwal, P. K., de Berg, M., Gao, J., Guibas, L. J., & Har-Peled, S. (2005). 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.
Agarwal, Pankaj K. ; de Berg, Mark ; Gao, Jie ; Guibas, Leonidas J. ; Har-Peled, Sariel. / Staying in the middle : exact and approximate medians in R1 and R2 for moving points. Paper presented at 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada.4 p.
@conference{666c3812069f4ec38cb8bbdd56e8ffba,
title = "Staying in the middle: exact and approximate medians in R1 and R2 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 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.",
author = "Agarwal, {Pankaj K.} and {de Berg}, Mark and Jie Gao and Guibas, {Leonidas J.} and Sariel Har-Peled",
year = "2005",
month = "1",
day = "1",
language = "English",
pages = "43--46",
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 R1 and R2 for moving points' Paper presented at 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada, 10/08/05 - 12/08/05, pp. 43-46.

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.

2005. 43-46 Paper presented at 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada.

Research output: Contribution to conferencePaperAcademic

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

SP - 43

EP - 46

ER -

Agarwal PK, de Berg M, Gao J, Guibas LJ, Har-Peled S. Staying in the middle: exact and approximate medians in R1 and R2 for moving points. 2005. Paper presented at 17th Canadian Conference on Computational Geometry, CCCG 2005, Windsor, Canada.