Понятие центральной точки является обобщением понятия медианы в статистике и вычислительной геометрий до данных в многомерных евклидовых пространствах. Если дано множество точек в d-мерном пространстве, центральная точка множества — это точка, такая что любая гиперплоскость, проходящая через эту точку, делит множество точек на две примерно равных подмножества: меньшая часть должна содержать как минимум долю точек. Подобно медиане центральная точка не обязательно единственна для набора точек. Любое непустое множество точек (без дубликатов) имеет как минимум одну центральную точку.

Связанные концепции Тесно связанной концепцией являются глубина Тьюки точки (минимальное число точек выборки на одной из сторон гиперплоскости, проходящей через точку) и медиана Тьюки набора точек (точка с максиальной глубиной Тьюки). Центральная точка — это точка с глубиной не менее , и медиана Тьюки обязательно является центральной, но не всякая центральная точка является медианой Тьюки. Глубина и медиана Тьюки носят имя Джона Тьюки.

О другом обобщении медианы для высоких размерностей смотрите статью Геометрический центр.

Существование Простое доказательство существования центральной точки можно получить при использовании теоремы Хелли. Допустим, имеется n точек, и рассмотрим семейство замкнутых полупространств, которые содержат более точек. Из любого такого полупространства исключается менее точек, поэтому пересечение любого подмножества из таких полупространств должно быть непустым. Согласно теореме Хелли, отсюда следует, что пересечение всех этих полупространств также должно быть непустым. Любая точка, принадлежащая этому пересечению, является центральной точкой.

Алгоритмы Для точек на плоскости центральная точка могут быть построена за линейное время. В любой размерности d медиана Тьюки (а потому и центральная точка) может быть построена за время .

Вероятностный алгоритм который многократно заменяет наборы из точек их точкой Радона может быть использован для вычисления аппроксимации центральной точки любого набора точек. Это означает, что его глубина по Тьюки линейно зависит от размера выборки, а время работы полиномиально зависит от размерности.

Примечания

Литература

. . . . .

Категория:Евклидова геометрия Категория:Многомерная евклидова геометрия Категория:Средние величины