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

Вы́пуклый слой^{[комм 1]} непустого конечного множества точек на плоскости — все точки этого множества, лежащие на границе его выпуклой оболочки, то есть вершины самого большого по площади выпуклого многоугольника (или концы отрезка, когда все точки лежат на одной прямой) с вершинами в точках множества^{[1][2][3][4][5]}.

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

В соответствии с общепринятой практикой не только собственно выпуклая оболочка ${\displaystyle \operatorname {Conv} (S)}$, но также и её граница ${\displaystyle \operatorname {CH} (S)}$ называются выпуклой оболочкой, а выпуклая оболочка обозначаться ${\displaystyle \operatorname {CH} (S)}$^[6].

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

Выпуклые слои плоского множества из ${\displaystyle n}$ точек можно найти за оптимальное время ${\displaystyle \Theta (n\ln n)}$➤^[7][2].

Выпуклые слои — один из двух способов разложить всё точечное множество на непересекающиеся слои. Другой способ — максимальные слои^[1][5].

Набор всех выпуклых слоёв плоского множества можно сравнить с разложением луковицы на слои^[8].

Луковое разложение^{[комм 1]}, или луковица^{[комм 1]}, множества точек — множество всех выпуклых слоёв этого множества точек^[4][3].

Шелушение^{[комм 1]}, или лущение^{[комм 1]}, множества точек — процесс представления этого множества в виде луковицы^[4][8].

Общее положение исходного множества точек заключается в том, что все его точки различны и никакие три точки не лежат на одной прямой. Если количество точек исходного множества в общем положении больше 2, то среди его выпуклых слоёв имеется по крайней мере один выпуклый двумерный многоугольник^[5]. Обычно в статьях по вычислительной геометрии подразумевается именно это общее положение множества точек^{[1][2][3][4][5]}.

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

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

Формальное определение выпуклых слоёв^{[комм 1]} — рекурсивное с использованием обозначений^[1].

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

В соответствии с общепринятой практикой не только собственно выпуклая оболочка ${\displaystyle \operatorname {Conv} (S)}$, но также и её граница ${\displaystyle \operatorname {CH} (S)}$ называются выпуклой оболочкой, а выпуклая оболочка может обозначаться ${\displaystyle \operatorname {CH} (S)}$^[6].

Луковое разложение^{[комм 1]}, или луковица^{[комм 1]}, ${\displaystyle C(S)}$ множества точек ${\displaystyle S}$ — множество всех выпуклых слоёв этого множества точек^[4][3].

Шелушение^{[комм 1]}, или лущение^{[комм 1]}, множества точек ${\displaystyle C(S)}$ — процесс представления этого множества в виде луковицы ${\displaystyle C(S)}$^[4][8].

Общее положение исходного множества точек заключается в том, что все его точки различны и никакие три точки не лежат на одной прямой. Если количество точек исходного множества в общем положении больше 2, то среди его выпуклых слоёв имеется по крайней мере один выпуклый двумерный многоугольник^[5]. Обычно в статьях по вычислительной геометрии подразумевается именно это общее положение множества точек. Тогда выпуклый слой множества — вершины самого большого по вложенности выпуклого многоугольника с вершинами в точках множества^{[1][2][3][4][5]}.

Количество слоёв лукового разложения ${\displaystyle C(S)}$ множества точек ${\displaystyle S}$ — число ${\displaystyle k}$ такое, что ${\displaystyle S_{k}\neq \varnothing }$, но ${\displaystyle S_{k+1}=\varnothing }$^[4]:

${\displaystyle C(S)=\{C_{1},\,C_{2},\,\dots ,\,C_{k-1},\,C_{k}\}}$;

${\displaystyle S=S_{1}\supset S_{2}\supset \dots \supset S_{k-1}\supset S_{k}}$;

${\displaystyle C_{1}\subset \operatorname {CH} (S_{1})=\operatorname {CH} (S),\,C_{2}\subset \operatorname {CH} (S_{2}),\,\dots ,}$

${\displaystyle C_{k-1}\subset \operatorname {CH} (S_{k-1}),\,C_{k}=S_{k}}$;

${\displaystyle C_{1}\cap C_{2}=\dots =C_{k-1}\cap C_{k}=\varnothing }$;

${\displaystyle C_{1}\cup C_{2}\cup \dots \cup C_{k-1}\cup C_{k}=S_{1}=S}$,

${\displaystyle C_{2}\cup \dots \cup C_{k-1}\cup C_{k}=S_{2}}$, ${\displaystyle \,\,\dots }$, ${\displaystyle \,\,C_{k}=S_{k}}$.

Обозначим через ${\displaystyle h_{i}}$ количество точек в слое ${\displaystyle C_{i}}$, а через

${\displaystyle H_{i}=h_{1}+h_{2}+\cdots +h_{i}}$ —

количество точек «толстого слоя»

${\displaystyle C_{1}\cup C_{2}\cup \dots \cup C_{i}}$,

получается, что ${\displaystyle H_{i}=H_{i-1}+h_{i}}$, ${\displaystyle i>1}$^[5].

Предложение 1. Если множество точек ${\displaystyle S}$ находится в общем положении, то есть все его точки различны и никакие три точки не лежат на одной прямой, то ${\displaystyle H_{i}\geqslant \min(3i,\,n)}$^[5].

Вычисление первых выпуклых слоев плоского множества точек в общем положении имеет многочисленные приложения, например, используется в качестве первого шага при вычислении^[5]:

• ${\displaystyle k}$-множеств^[англ.] (или двойственно ${\displaystyle k}$-уровней^[англ.]);
• ${\displaystyle k}$-оболочек (или двойственно ${\displaystyle k}$-поясов).

${\displaystyle k}$-множество, или ${\displaystyle k}$-уровень, заданного множества ${\displaystyle S}$ — пересечение множества ${\displaystyle S}$ с некоторой полуплоскостью ${\displaystyle H}$, ${\displaystyle S\cup H}$, такое, что количество элементов множества ${\displaystyle |S\cup H|=k}$^[5].

${\displaystyle k}$-оболочка, или ${\displaystyle k}$-пояс, заданного множества ${\displaystyle S}$ — множество точек ${\displaystyle p\in S}$ такое, что для любой прямой, проходящей через ${\displaystyle p}$, в каждой из двух замкнутых полуплоскостей, определяемых этой прямой, есть по крайней мере ${\displaystyle k\leqslant \left\lfloor {n \over 2}\right\rfloor }$ точек из ${\displaystyle S}$^[5].

Предложение 2. Из определения следует, что ${\displaystyle k}$-оболочка содержит множество точек ${\displaystyle S_{k}}$^[5].

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

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

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

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

Геометрия и статистика тесно взаимосвязаны, поскольку многомерные статистические данные можно представить точками в евклидовом пространстве. В такой постановке задачи статистики превращаются в чисто геометрические задачи. Например, в некоторых задачах статистики базовый алгоритм — поиск выпуклой оболочки^[9].

Основная задача в статистике, согласно Ф. Препарата и М. Шеймоса^{[англ.][10]}, — оценивание параметров данной популяции, например, средние значения, на основе малой случайной выборки. Хорошая статистическая оценка обладает робастностью (устойчивостью), то есть слабой зависимостью от отклонения от моделируемого распределения популяции. Методы такой оценки основаны на концепции, когда наибольшее доверие заслуживают данные, наиболее близкие к «центру» выборки^[10].

Для обеспечения такой робастности удаляются периферийные точки, чтобы удалить предполагаемые выбросы, то есть наблюдения, существенно выпадающие из основной массы. Известен алгоритм под названием «лущение» или «шелушение», заключающийся в удалении выпуклой оболочки множества точек, затем снова в удалении выпуклой оболочки оставшегося множества, и так до некоторого предела, при таком подходе возникло понятие глубины множества^[8][2].

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

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

Отсюда возникает следующая геометрическая проблема, которая имеет и самостоятельный интерес^[8].

Проблема 1 (глубина множества). Найти глубину каждой точки множества на плоскости^[8].

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

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

Поиск в полуплоскости точек — один из типов задачи регионального поиска, когда ищутся все точки данного множества, лежащие в полуплоскости запроса^[12].

Для упрощения поиска на плоскости точек данного множества ${\displaystyle S}$, лежащих в полуплоскости запроса ${\displaystyle H}$, сначала ищется множество выпуклых слоёв

${\displaystyle C(S)=\{S_{1},\,S_{2},\,\dots ,\,S_{n}\}}$.

Пусть теперь ${\displaystyle l}$ — граница ${\displaystyle H}$. Предположим также, что ${\displaystyle l}$ пересекает ${\displaystyle S_{1}}$, то есть полуплоскость ${\displaystyle H}$ содержит по крайней мере одну точку множества ${\displaystyle S}$; в противном случае задача тривиальна: либо в ${\displaystyle H}$ нет точек из ${\displaystyle S}$, либо они все в полуплоскости. Определяем по очереди, пересекает ли прямая ${\displaystyle l}$ слои ${\displaystyle S_{1},\,S_{2},\,\dots ,\,S_{n}}$, и собираем вершины слоёв, лежащие в ${\displaystyle H}$. Процесс обрывается, когда ${\displaystyle l}$ не пересекает ${\displaystyle S_{i}}$. Это означает, что вместе с последующими слоями полуплоскость ${\displaystyle H}$ либо не содержит ни одной точки слоя ${\displaystyle S_{i}}$, либо содержит их все. Можно доказать, что множество оболочек ${\displaystyle S_{i}}$, пересекаемых ${\displaystyle l}$, образует начало последовательности ${\displaystyle S_{1},\,S_{2},\,\dots ,\,S_{n}}$. Пусть ${\displaystyle S_{1},\,S_{2},\,\dots ,\,S_{m}}$ — это те слои, которые пересекает ${\displaystyle l}$. Тогда слой ${\displaystyle S_{m}}$ называется соседним слоем прямой ${\displaystyle l}$^[13].

1. ↑ ^{1 2 3 4 5 6 7 8 9 10} Имеется перевод на английский язык.

1. ↑ ^{1 2 3 4 5 6 7 8 9} Кормен Т. Алгоритмы: построение и анализ, 2011, Глава 33. Вычислительная геометрия. 33-1. Выпуклые слои, с. 1080.
2. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12} Bernard Chazelle. On the convex layers of a planar set, 1985, p. 509.
3. ↑ ^{1 2 3 4 5} Bernard Chazelle. The power of geometric duality, 1985, 4. The half-plane range query problem, с. 85.
4. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12} Maarten Löffler, Wolfgang Mulzer. Unions of onions: preprocessing imprecise points for fast onion decomposition, 2014, p. 1, 3.
5. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12 13 14} Franck Nielsen. Output-sensitive peeling of convex and maximal layers, 1996, p. 255.
6. ↑ ^{1 2} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 3.1. Предварительные сведения, с. 119.
7. ↑ ^{1 2} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.2.1. Робастное оценивание, с. 213.
8. ↑ ^{1 2 3 4 5 6 7 8} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.2.1. Робастное оценивание, с. 211.
9. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.2. Приложения в статистике, с. 210.
10. ↑ ^{1 2} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.2.1. Робастное оценивание, с. 210.
11. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.2.1. Робастное оценивание, с. 212.
12. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 2.4. Замечания и комментарии, с. 112.
13. ↑ Bernard Chazelle. The power of geometric duality, 1985, 4. The half-plane range query problem, с. 85—86.

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. Second edition (рус.) / пер. с англ. канд. техн. наук И. В. Красикова, Н. А. Ореховой, В. Н. Романова под ред. канд. техн. наук И. В. Красикова. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — 1290 с., ил. — 1000 экз. — ISBN 978-5–8459–0857–5 (рус.). — ISBN 0–07–013151–1 (англ.).
• Препарата Ф., Шеймос М.^[англ.]. Вычислительная геометрия. Введение = Franco P. Preparata, Michael Ian Shamos. Computational geometry. An introduction (рус.) / пер. с англ. С. А. Вичеса, М. М. Комарова под ред. Ю. М. Баяковского. — М.: «Мир», 1989. — 478 с., ил. — 10 000 экз. — ISBN 5-03-001041-6 (русск.). — ISBN 0-387-96131-3 (англ.).
• Bernard Chazelle^[англ.]. On the convex layers of a planar set (англ.) // IEEE Transactions on Information Theory^[англ.], issn 0018-9448 (Print) : журнал. — New York City: Institute of Electrical and Electronics Engineers, 1985. — Vol. 31, no. 4. — P. 509—517. — ISSN 1557-9654. — doi:10.1109/TIT.1985.1057060.
• Bernard Chazelle^[англ.], Leo J. Guibas^[англ.], D. T. Lee^[англ.]. The power of geometric duality (англ.) // BIT^[англ.], issn 0006-3835 (Print) : журнал. — Lund: BIT Foundation, 1985. — Vol. 25. — P. 76—90. — ISSN 1572-9125. — doi:10.1007/BF01934990.
• Maarten Löffler, Wolfgang Mulzer. Unions of onions: preprocessing imprecise points for fast onion decomposition (англ.) // Journal of Computational Geometry^[англ.] : журнал. — Ottawa: MacOdrum Library, Carleton University, 2014. — Vol. 5, no. 1. — P. 1—13. — ISSN 1920-180X. — doi:10.20382/jocg.v5i1a1.
• Franck Nielsen. Output-sensitive peeling of convex and maximal layers (англ.) // Information Processing Letters^[англ.] : журнал / editor: Leah Epstein. — Amsterdam: Elsevier, 1996. — Vol. 59, iss. 5. — P. 255—259. — ISSN 0020-0190. — doi:10.1016/0020-0190(96)00116-0.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.