Выпуклые слои - Википедия - Convex layers

Выпуклые слои множества точек и их пересечение с полуплоскостью

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

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

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

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

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

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