Центральная точка (геометрия)
-
Понятие центральной точки
- Центральная точка обобщает медиану на многомерные данные.
- Центральная точка делит набор точек на два примерно равных подмножества.
- Центральная точка не обязательно должна быть одной из точек данных.
-
Связанные понятия
- Глубина Тьюки точки — минимальное количество точек на одной стороне гиперплоскости.
- Медиана Тьюки — точка, максимизирующая глубину Тьюки.
- Центральная точка имеет глубину не менее n/(d + 1).
- Медиана Тьюки должна быть центральной точкой, но не каждая центральная точка является медианой Тьюки.
-
Существование центральной точки
- Теорема Хелли доказывает существование центральной точки.
- Пересечение всех полупространств должно быть непустым, что означает существование центральной точки.
-
Алгоритмы
- Центральная точка на евклидовой плоскости строится за линейное время.
- Медиана Тьюки и центральная точка могут быть построены за время O(nd − 1 + n log n).
- Рандомизированный алгоритм позволяет вычислить приближение к центральной точке за полиномиальное время.