Центральная точка (геометрия) - Centerpoint (geometry) - Wikipedia

В статистика и вычислительная геометрия, понятие Центральная точка является обобщением медиана к данным в многомерном Евклидово пространство. Учитывая набор точек в d-мерное пространство, центральная точка множества - это такая точка, что любая гиперплоскость, которая проходит через эту точку, делит множество точек на два примерно равных подмножества: меньшая часть должна иметь как минимум 1 / (d + 1) доля очков. Как и медиана, центральная точка не обязательно должна быть одной из точек данных. Каждый непустой набор точек (без дубликатов) имеет по крайней мере одну центральную точку.

Связанные понятия

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

Для другого обобщения медианы на более высокие измерения см. геометрическая медиана.

Существование

Простое доказательство существования центральной точки можно получить, используя Теорема Хелли. Предположим, есть п точек, и рассмотрим семейство замкнутых полупространства которые содержат более дн/(d + 1) очков. Меньше чем п/(d +1) точки исключаются из любого из этих полупространств, поэтому пересечение любого подмножества d +1 из этих полупространств должно быть непустым. По теореме Хелли следует, что пересечение всех этих полупространств также должно быть непустым. Любая точка на этом пересечении обязательно является центральной точкой.

Алгоритмы

Для очков в Евклидова плоскость, центральную точку можно построить в линейное время.[1] В любом измерении d, медиана Тьюки (и, следовательно, также центральная точка) может быть построена за время O (пd − 1 + п бревноп).[2]

А рандомизированный алгоритм который неоднократно заменяет наборы d + 2 балла по их радоновой точке могут быть использованы для вычисления приближение к центральной точке любого набора точек в том смысле, что его глубина Тьюки линейна по размеру набора выборки, в течение времени, полиномиального как по количеству точек, так и по размеру.[3]

Рекомендации

Цитаты

  1. ^ Джадхав и Мукхопадхьяй (1994).
  2. ^ Чан (2004).
  3. ^ Кларксон и др. (1996).

Источники

  • Чан, Тимоти М. (2004), «Оптимальный рандомизированный алгоритм для максимальной глубины Тьюки», Proc. 15-й симпозиум ACM – SIAM. по дискретным алгоритмам (SODA 2004), стр. 430–436.
  • Кларксон, Кеннет Л.; Эппштейн, Дэвид; Миллер, Гэри Л.; Стуртивант, Карл; Тэн, Шан-Хуа (Сентябрь 1996 г.), «Аппроксимация центральных точек повторяющимися точками Радона» (PDF), Международный журнал вычислительной геометрии и приложений, 6 (3): 357–377, МИСТЕР  1409651.
  • Эдельсбруннер, Герберт (1987), Алгоритмы комбинаторной геометрии, Берлин: Springer-Verlag, ISBN  0-387-13722-X.
  • Jadhav, S .; Mukhopadhyay, A. (1994), "Вычисление центральной точки конечного плоского набора точек за линейное время", Дискретная и вычислительная геометрия, 12 (1): 291–312, Дои:10.1007 / BF02574382.