Выпуклые слои

В вычислительной геометрии выпуклые слои набора точек евклидовой плоскости представляют собой последовательность вложенных выпуклых многоугольников , вершинами которых являются точки. Самая внешняя — это выпуклая оболочка точек, остальные формируются таким же рекурсивным способом . Самый внутренний слой может быть вырожденным и состоять всего из одной или двух точек. ^[1]Задачу построения выпуклых слоев еще называют луковой шелухой или разложением лука . ^[2]

Хотя построение выпуклых слоев путем многократного поиска выпуклых оболочек будет медленнее, можно разделить любой набор $n$ указывает на его выпуклые слои во времени $O(n\log n)$ . ^[1]

Первое применение выпуклых слоев было в надежной статистике как способ выявления выбросов и измерения центральной тенденции набора точек выборки. ^[3]^[4] В этом контексте количество выпуклых слоев, окружающих данную точку, называется глубиной отслаивания ее выпуклой оболочки , а сами выпуклые слои являются контурами глубины для этого понятия глубины данных. ^[5]

Выпуклые слои могут использоваться как часть эффективной структуры данных отчета о диапазоне для перечисления всех точек в полуплоскости запроса . Точки в полуплоскости каждого последующего слоя могут быть найдены с помощью бинарного поиска, чтобы найти самую крайнюю точку в направлении полуплоскости, а затем выполнить последовательный поиск оттуда. Дробное каскадирование можно использовать для ускорения двоичного поиска, сокращая общее время запроса. $O(\log n+k)$ найти $k$ точки из набора $n$ . ^[6]

Точки $n\times n$ сетка есть $\Theta (n^{4/3})$ выпуклые слои, ^[7] как и то же количество равномерно случайных точек внутри любой выпуклой формы. ^[8]

Ссылки

^ Jump up to: ^а ^б Шазель, Бернар (1985), «О выпуклых слоях плоского множества», IEEE Trans. Инф. Theory , 31 (4): 509–517, CiteSeerX 10.1.1.113.8709 , doi : 10.1109/TIT.1985.1057060 , MR 0798557
^ Леффлер, Мартен; Мульцер, Вольфганг (2014), «Объединения луковиц: предварительная обработка неточных точек для быстрого разложения луковиц», Журнал вычислительной геометрии , 5 (1): 1–13, arXiv : 1302.5328 , doi : 10.20382/jocg.v5i1a1 , MR 3162956 , S2CID 6679520 .
^ Барнетт, В. (1976), «Упорядочение многомерных данных», Дж. Рой. Статист. Соц. Сер. A , 139 (3): 318–355, doi : 10.2307/2344839 , JSTOR 2344839 , MR 0445726 , S2CID 117008915.
^ Эдди, В. Ф. (1982), «Отслаивание выпуклой оболочки», 5-й симпозиум COMPSTAT 1982 г., состоявшийся в Тулузе, 1982 г. , Physica-Verlag, стр. 42–47 , doi : 10.1007/978-3-642-51461-6_4 , ISBN 978-3-7051-0002-2
^ Лю, Регина Ю .; Парелиус, Джесси М.; Сингх, Кесар (1999), «Многомерный анализ по глубине данных: описательная статистика, графики и выводы», Annals of Статистика , 27 (3): 783–858, doi : 10.1214/aos/1018031260 , MR 1724033
^ Шазель, Бернар ; Гибас, Лео Дж .; Ли, Д.Т. (1985), «Сила геометрической двойственности», BIT , 25 (1): 76–90, doi : 10.1007/BF01934990 , MR 0785806
^ Хар-Пелед, Сариэль ; Лидицкий, Бернард (2013), «Очистка сетки», SIAM Journal on Discrete Mathematics , 27 (2): 650–655, arXiv : 1302.3200 , doi : 10.1137/120892660 , MR 3040367 , S2CID 15837161
^ Далал, Кетан (2004), «Подсчет лука», Случайные структуры и алгоритмы , 24 (2): 155–165, doi : 10.1002/rsa.10114 , MR 2035873 , S2CID 10366666

[c85-1] Jump up to: ^а ^б Шазель, Бернар (1985), «О выпуклых слоях плоского множества», IEEE Trans. Инф. Theory , 31 (4): 509–517, CiteSeerX 10.1.1.113.8709 , doi : 10.1109/TIT.1985.1057060 , MR 0798557

[2] Леффлер, Мартен; Мульцер, Вольфганг (2014), «Объединения луковиц: предварительная обработка неточных точек для быстрого разложения луковиц», Журнал вычислительной геометрии , 5 (1): 1–13, arXiv : 1302.5328 , doi : 10.20382/jocg.v5i1a1 , MR 3162956 , S2CID 6679520 .

[3] Барнетт, В. (1976), «Упорядочение многомерных данных», Дж. Рой. Статист. Соц. Сер. A , 139 (3): 318–355, doi : 10.2307/2344839 , JSTOR 2344839 , MR 0445726 , S2CID 117008915.

[4] Эдди, В. Ф. (1982), «Отслаивание выпуклой оболочки», 5-й симпозиум COMPSTAT 1982 г., состоявшийся в Тулузе, 1982 г. , Physica-Verlag, стр. 42–47 , doi : 10.1007/978-3-642-51461-6_4 , ISBN 978-3-7051-0002-2

[5] Лю, Регина Ю .; Парелиус, Джесси М.; Сингх, Кесар (1999), «Многомерный анализ по глубине данных: описательная статистика, графики и выводы», Annals of Статистика , 27 (3): 783–858, doi : 10.1214/aos/1018031260 , MR 1724033

[6] Шазель, Бернар ; Гибас, Лео Дж .; Ли, Д.Т. (1985), «Сила геометрической двойственности», BIT , 25 (1): 76–90, doi : 10.1007/BF01934990 , MR 0785806

[7] Хар-Пелед, Сариэль ; Лидицкий, Бернард (2013), «Очистка сетки», SIAM Journal on Discrete Mathematics , 27 (2): 650–655, arXiv : 1302.3200 , doi : 10.1137/120892660 , MR 3040367 , S2CID 15837161

[8] Далал, Кетан (2004), «Подсчет лука», Случайные структуры и алгоритмы , 24 (2): 155–165, doi : 10.1002/rsa.10114 , MR 2035873 , S2CID 10366666

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]