Центральная точка (геометрия)
В статистике и вычислительной геометрии понятие центральной точки является обобщением медианы для данных в многомерном евклидовом пространстве . Учитывая набор точек в d -мерном пространстве, центральной точкой набора является такая точка, что любая гиперплоскость, проходящая через эту точку, делит набор точек на два примерно равных подмножества: меньшая часть должна иметь как минимум 1/( d +1) доля баллов. Как и медиана, центральная точка не обязательно должна быть одной из точек данных. Каждый непустой набор точек (без дубликатов) имеет хотя бы одну центральную точку.
Связанные понятия
[ редактировать ]Тесно связанными понятиями являются глубина Тьюки точки (минимальное количество точек выборки на одной стороне гиперплоскости, проходящей через точку) и медиана Тьюки набора точек (точка, максимизирующая глубину Тьюки). Центральная точка — это точка глубины не менее n /( d + 1), а медиана Тьюки должна быть центральной точкой, но не каждая центральная точка является медианой Тьюки. Оба термина названы в честь Джона Тьюки .
Чтобы узнать о другом обобщении медианы на более высокие измерения, см. геометрическую медиану .
Существование
[ редактировать ]Простое доказательство существования центральной точки можно получить с помощью теоремы Хелли . Предположим, что имеется n точек, и рассмотрим семейство замкнутых полупространств , содержащее более dn /( d + 1) точек. Менее n /( d + 1) точек исключено из любого из этих полупространств, поэтому пересечение любого подмножества из d + 1 этих полупространств должно быть непустым. По теореме Хелли отсюда следует, что пересечение всех этих полупространств также должно быть непусто. Любая точка этого пересечения обязательно является центральной точкой.
Алгоритмы
[ редактировать ]Для точек евклидовой плоскости центральная точка может быть построена за линейное время . [1] В любом измерении d медиана Тьюки (и, следовательно, также центральная точка) может быть построена за время O( n д - 1 + n журнал n ). [2]
, Рандомизированный алгоритм который неоднократно заменяет наборы из d + 2 точек их точкой Радона , может использоваться для вычисления приближения к центральной точке любого набора точек в том смысле, что его глубина Тьюки линейна в зависимости от размера набора выборок, в количестве время, полиномиальное по размерности. [3] [4]
Ссылки
[ редактировать ]Цитаты
[ редактировать ]Источники
[ редактировать ]- Чан, Тимоти М. (2004), «Оптимальный рандомизированный алгоритм для максимальной глубины Тьюки», Proc. 15-й симпозиум ACM – SIAM. по дискретным алгоритмам (SODA 2004) , стр. 430–436, ISBN 978-0-89871-558-3 .
- Кларксон, Кеннет Л .; Эппштейн, Дэвид ; Миллер, Гэри Л .; Стертивант, Карл; Тенг, Шан-Хуа (сентябрь 1996 г.), «Аппроксимация центральных точек с помощью итерированных точек Радона» (PDF) , International Journal of Computational Geometry & Applications , 6 (3): 357–377, doi : 10.1142/S021819599600023X , MR 1409651 .
- Эдельсбруннер, Герберт (1987), Алгоритмы в комбинаторной геометрии , Берлин: Springer-Verlag, ISBN 0-387-13722-Х .
- Джадхав, С.; Мукхопадьяй, А. (1994), «Вычисление центральной точки конечного плоского набора точек за линейное время», Дискретная и вычислительная геометрия , 12 (1): 291–312, doi : 10.1007/BF02574382 .
- Хар-Пелед, С.; Джонс, М. (31 декабря 2020 г.), «Путешествие к центру множества точек» , Транзакции ACM в алгоритмах , 17 (1): 9:1–9:21, doi : 10.1145/3431285 , ISSN 1549- 6325 .