Pilz, Alexander ;
Schnider, Patrick
Extending the Centerpoint Theorem to Multiple Points
Abstract
The centerpoint theorem is a wellknown and widely used result in discrete geometry. It states that for any point set P of n points in R^d, there is a point c, not necessarily from P, such that each halfspace containing c contains at least n/(d+1) points of P. Such a point c is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for the point set P. But what if we allow more than one representative? For example in onedimensional data sets, often certain quantiles are chosen as representatives instead of the median.
We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set Q of (few) points such that every halfspace that contains one point of Q contains a large fraction of the points of P and every halfspace that contains more of Q contains an even larger fraction of P. This setting is comparable to the wellstudied concepts of weak epsilonnets and weak epsilonapproximations, where it is stronger than the former but weaker than the latter. We show that for any point set of size n in R^d and for any positive alpha_1,...,alpha_k where alpha_1 <= alpha_2 <= ... <= alpha_k and for every i,j with i+j <= k+1 we have that (d1)alpha_k+alpha_i+alpha_j <= 1, we can find Q of size k such that each halfspace containing j points of Q contains least alpha_j n points of P. For twodimensional point sets we further show that for every alpha and beta with alpha <= beta and alpha+beta <= 2/3 we can find Q with Q=3 such that each halfplane containing one point of Q contains at least alpha n of the points of P and each halfplane containing all of Q contains at least beta n points of P. All these results generalize to the setting where P is any mass distribution. For the case where P is a point set in R^2 and Q=2, we provide algorithms to find such points in time O(n log^3 n).
BibTeX  Entry
@InProceedings{pilz_et_al:LIPIcs:2018:10001,
author = {Alexander Pilz and Patrick Schnider},
title = {{Extending the Centerpoint Theorem to Multiple Points}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {53:153:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10001},
URN = {urn:nbn:de:0030drops100019},
doi = {10.4230/LIPIcs.ISAAC.2018.53},
annote = {Keywords: centerpoint, point sets, Tukey depth}
}
06.12.2018
Keywords: 

centerpoint, point sets, Tukey depth 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 