10.4230/LIPICS.ISAAC.2018.53
Pilz, Alexander
Alexander
Pilz
https://orcid.org/0000-0002-6059-1821
Institute of Software Technology, Graz University of Technology, Austria
Schnider, Patrick
Patrick
Schnider
Department of Computer Science, ETH Zurich, Switzerland
Extending the Centerpoint Theorem to Multiple Points
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2018
centerpoint
point sets
Tukey depth
Hsu, Wen-Lian
Wen-Lian
Hsu
Lee, Der-Tsai
Der-Tsai
Lee
Liao, Chung-Shou
Chung-Shou
Liao
2018
2018-12-06
2018-12-06
2018-12-06
en
urn:nbn:de:0030-drops-100019
arXiv:1810.10231
10.4230/LIPIcs.ISAAC.2018
978-3-95977-094-1
1868-8969
10.1016/S0167-9473(02)00032-4
10.1016/j.comgeo.2008.02.005
http://www.cs.queensu.ca/cccg/papers/cccg13.pdf
10.1007/978-3-319-44479-6_12
10.1007/BF02187876
10.1007/BF02574382
10.1007/3-540-36494-3_6
10.1007/BF02187804
10.1007/BF02574066
10.1007/BF01303517
https://hal.archives-ouvertes.fr/hal-01468664
10.1016/j.comgeo.2007.10.004
10.1007/s00373-007-0716-1
10.4230/LIPIcs.ISAAC.2018
LIPIcs, Volume 123, ISAAC 2018
29th International Symposium on Algorithms and Computation (ISAAC 2018)
2019
123
53
53:1
53:13
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hsu, Wen-Lian
Wen-Lian
Hsu
Lee, Der-Tsai
Der-Tsai
Lee
Liao, Chung-Shou
Chung-Shou
Liao
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2018
123
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
13 pages
536914 bytes
application/pdf
Creative Commons Attribution 3.0 Unported license
info:eu-repo/semantics/openAccess
The centerpoint theorem is a well-known 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 one-dimensional 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 well-studied concepts of weak epsilon-nets and weak epsilon-approximations, 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 (d-1)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 two-dimensional 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).
LIPIcs, Vol. 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018), pages 53:1-53:13