Extending the Centerpoint Theorem to Multiple Points
OPEN ACCESS
Loading...
Author / Producer
Date
2018
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
External links
Editor
Book title
Volume
123
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
29th International Symposium on Algorithms and Computation (ISAAC 2018)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
centerpoint; point sets; Tukey depth
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)