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

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

Связанные концепции

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

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

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

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

Алгоритмы

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

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

Ссылки

Цитаты

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

Источники

• Чан, Тимоти М. (2004), «Оптимальный рандомизированный алгоритм для максимальной глубины Тьюки», Труды 15-го симпозиума ACM–SIAM по дискретным алгоритмам (SODA 2004), Общество промышленной и прикладной математики, стр. 430–436, ISBN 978-0-89871-558-3.
• Кларксон, Кеннет Л .; Эппштейн, Дэвид ; Миллер, Гэри Л.; Стертивант, Карл; Тенг, Шан-Хуа (сентябрь 1996 г.), «Аппроксимация центральных точек с помощью итерированных точек Радона» (PDF) , Международный журнал вычислительной геометрии и приложений , 6 (3): 357–377, doi :10.1142/S021819599600023X, MR  1409651.
• Эдельсбруннер, Герберт (1987), Алгоритмы в комбинаторной геометрии , Берлин: Springer-Verlag, ISBN 0-387-13722-X.
• Джадхав, С.; Мукхопадхай, А. (1994), «Вычисление центральной точки конечного плоского множества точек за линейное время», Дискретная и вычислительная геометрия , 12 (1): 291–312, doi : 10.1007/BF02574382.
• Хар-Пелед, С.; Джонс, М. (31.12.2020), «Путешествие к центру множества точек», ACM Transactions on Algorithms , 17 (1): 9:1–9:21, doi : 10.1145/3431285, ISSN  1549-6325.