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

Вы́пуклый слой (англ. convex layer) множества точек на плоскости — понятие вычислительной геометрии, раздела информатики, вершины выпуклой оболочки этого множества^[1][2][3].

Синоним: первый выпуклый слой^[1].

Второй выпуклый слой — выпуклый слой множества точек после удаления первого выпуклого слоя. Третий выпуклый слой — выпуклый слой множества точек после удаления первого и второго выпуклых слоёв. И так далее^[1][2][3].

Понятие выпуклых слоёв множества точек можно рассматривать как естественное расширение понятия выпуклой оболочки^[2].

Концепция выпуклых слоёв имеет приложения к распознаванию образов и статистике, а также в контексте метода частичного каскадирования^[англ.] — задаче отчёта о диапазоне^[англ.] полуплоскости^[2].

Набор всех выпуклых слоёв плоского множества можно сравнить с расслоённой луковицей (англ. onion decomposition), или, кратко, луковицей (англ. onion), а процесс получения этих слоёв — с «лущением», или «шелушением», луковицы (англ. onion peeling)^[3][4].

Следующее определение выпуклых слоёв — рекурсивное^[1].

Первый выпуклый слой множества ${\displaystyle S}$ точек на плоскости состоит из вершин выпуклой оболочки ${\displaystyle \operatorname {CH} (S)}$ этого множества. Пусть множество ${\displaystyle S_{i}}$, ${\displaystyle i>1}$, — это точки множества ${\displaystyle S}$ без всех точек выпуклых слоёв с номерами ${\displaystyle 1,\,2,\,\dots ,\,i-1}$. Тогда ${\displaystyle i}$-й выпуклый слой состоит из вершин выпуклой оболочки ${\displaystyle \operatorname {CH} (S_{i})}$, если множество точек ${\displaystyle S_{i}\neq \varnothing }$; иначе слой не определён^[1][3].

Теорема. Выпуклые слои плоского множества ${\displaystyle S}$ из ${\displaystyle n}$ точек можно построить за время ${\displaystyle O(n\operatorname {lg} n)}$ по любой вычислительной модели такой, что в ней сортировка ${\displaystyle n}$ вещественных чисел занимает время ${\displaystyle O(n\operatorname {lg} n)}$^[1][2].

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

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

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

Глубина точки ${\displaystyle P}$ множества ${\displaystyle S}$ точек на плоскости — номер выпуклого слоя, к которому принадлежит точка ${\displaystyle P}$^[4].

Глубина множества ${\displaystyle S}$ точек на плоскости — глубина его самой глубокой точки ${\displaystyle P}$, то есть количество непустых выпуклых слоёв^[4].

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

Теорема 2. Выпуклые слои плоского множества ${\displaystyle S}$ из ${\displaystyle n}$ точек, а заодно и глубину множества ${\displaystyle S}$, можно найти за оптимальное время ${\displaystyle O(n\operatorname {lg} n)}$^[6].

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильямс», 2011. 1290 с.: ил. Парал. тит. англ. ISBN 978-5–8459–0857–5 (рус.) [Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms. Second edition. Cambridge, Massachusetts · London, England: MIT Press, 2002.]
• Препарата Ф., Шеймос М.^[англ.]. Вычислительная геометрия: Введение. Пер. с англ. С. А. Вичеса, М. М. Комарова под ред. Ю. М. Банковского. М.: «Мир», 1989. 478 с. ISBN 5-03-001041-6. [Franco P. Preparata, Michael Ian Shamos, Computational geometry. An introduction. New York · Berlin · Heidelberg · Tokyo: Springer-Verlag, 1985.]
• Chazelle B.^[англ.] On the Convex Layers of a Planar Set // IEEE Transactions on Information Theory. 1985. Vol. IT-31. No. 4. P. 509–517.
• Maarten Löffler, Wolfgang Mulzer. Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition // Journal of Computational Geometry. 2014. Vol. 5(1). No. 4. P. 1–13.

Статья является кандидатом в добротные статьи с 24 февраля 2025.