Выпуклый слой (вычислительная геометрия)

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

Слои луковицы

Вы́пуклый слой (Шаблон:Lang-en) множества точек на плоскости — понятие вычислительной геометрии, раздела информатики, вершины выпуклой оболочки этого множестваШаблон:SfnШаблон:SfnШаблон:Sfn.

Синоним: первый выпуклый слойШаблон:Sfn.

Второй выпуклый слой — выпуклый слой множества точек после удаления первого выпуклого слоя. Третий выпуклый слой — выпуклый слой множества точек после удаления первого и второго выпуклых слоёв. И так далееШаблон:SfnШаблон:SfnШаблон:Sfn.

Понятие выпуклых слоёв множества точек можно рассматривать как естественное расширение понятия выпуклой оболочкиШаблон:Sfn.

Концепция выпуклых слоёв имеет приложения к [[Распознавание образов|распознаванию образов] и статистике, а также в контексте метода Шаблон:Iw — задаче Шаблон:Iw полуплоскостиШаблон:Sfn.

Набор всех выпуклых слоёв плоского множества можно сравнить с расслоённой луковицей (Шаблон:Lang-en), или, кратко, луковицей (Шаблон:Lang-en), а процесс получения этих слоёв — с «лущением», или «шелушением», луковицы (Шаблон:Lang-en)Шаблон:SfnШаблон:Sfn.

Определение выпуклых слоёв

Следующее определение выпуклых слоёв — рекурсивноеШаблон:Sfn.

Первый выпуклый слой множества $S$ точек $P$ на плоскости состоит из вершин выпуклой оболочки $\mathrm{CH}(S)$ этого множества. Пусть множество $S_i$, $i>1$, — это точки $P$ множества $S$ без всех точек выпуклых слоёв с номерами $1,2,\dots ,i-1$. Тогда Шаблон:S выпуклый слой состоит из вершин выпуклой оболочки $\mathrm{CH}(S_i)$, если множество точек $S_i\ne \varnothing$; иначе слой не определёнШаблон:SfnШаблон:Sfn.

Теорема. Выпуклые слои плоского множества $S$ из $n$ точек можно построить за время $O(n\lg n)$ по любой вычислительной модели такой, что в ней сортировка $n$ вещественных чисел занимает время $O(n\lg n)$Шаблон:SfnШаблон:Sfn.

Кроме практической значимости, проблема определения выпуклых слоев множества точек интересна сама по себе как геометрический «эквивалент» сортировке. Различные алгоритмы вычисления выпуклой оболочки множества точек позволяют провести параллель с различными алгоритмами сортировкиШаблон:Sfn:

• алгоритм Джарвиса выглядит как сортировка выбором;
• алгоритм типа «Разделяй и властвуй» Шаблон:Iw и Шаблон:Iw — сортировка слиянием;
• алгоритм Эдди — быстрая сортировка.

Но вычисление выпуклых оболочек проще, чем сортировка, поскольку выход алгоритма вычисления оболочки может содержать лишь небольшую часть исходных точек, тогда как алгоритм сортировки выдаёт все точки. Один из способов преодоления этого разрыва в сложности — требование вычисления всех выпуклых слоев множества точекШаблон:Sfn.

Глубина точки

Глубина точки $P$ множества $S$ точек на плоскости — номер выпуклого слоя, к которому принадлежит точка $P$Шаблон:Sfn.

Глубина множества $S$ точек на плоскости — глубина его самой глубокой точки $P$, то есть количество непустых выпуклых слоёвШаблон:Sfn.

Теорема 1. Произвольному алгоритму, вычисляющему глубину каждой точки $P$ плоского множества $S$ из $n$ точек, требуется $\mathrm{\Omega }(n\lg n)$ сравнений в худшем случаеШаблон:Sfn.

Теорема 2. Выпуклые слои плоского множества $S$ из $n$ точек, а заодно и глубину множества $S$, можно найти за оптимальное время $O(n\lg n)$Шаблон:Sfn.

Источники

• Шаблон:H
• Шаблон:H
• Шаблон:H
• Шаблон:H