2018/10/24 by Pilz, Alexander, Schnider, Patrick
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1810.10231
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 ℝ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 ε-nets and weak ε-approximations, where it is stronger than the former but weaker than the latter.