Выпуклая оболочка¶

Выпуклая оболочка — это минимальное выпуклое множество, содержащее заданное множество точек (или более общее множество) в евклидовом пространстве или в аффинном пространстве над вещественными числами. Интуитивно, если представить точки как гвозди, вбитые в доску, то выпуклая оболочка — это форма, которую примет туго натянутая вокруг них резиновая лента. Формально, выпуклая оболочка множества \(S\) — это пересечение всех выпуклых множеств, содержащих \(S\). Для конечного набора точек на плоскости выпуклая оболочка представляет собой выпуклый многоугольник, вершинами которого являются некоторые из исходных точек.

¶Определение и основные свойства

Пусть \(S\) — подмножество векторного пространства \(\mathbb{R}^n\). Выпуклой оболочкой \(\operatorname{conv}(S)\) называется множество всех выпуклых комбинаций точек из \(S\):

\[ \operatorname{conv}(S) = \left\{ \sum_{i=1}^{k} \lambda_i x_i \mid x_i \in S,\ \lambda_i \ge 0,\ \sum_{i=1}^{k} \lambda_i = 1,\ k \in \mathbb{N} \right\}. \]

Ключевые свойства:

• Выпуклость: \(\operatorname{conv}(S)\) само является выпуклым множеством.
• Минимальность: \(\operatorname{conv}(S)\) содержится в любом выпуклом множестве, содержащем \(S\).
• Идемпотентность: \(\operatorname{conv}(\operatorname{conv}(S)) = \operatorname{conv}(S)\).
• Для компактного множества \(S\) его выпуклая оболочка также компактна (теорема Каратеодори о выпуклой оболочке).
• Для конечного набора точек выпуклая оболочка является выпуклым многогранником (политопом).

¶История

Понятие выпуклой оболочки восходит к работам древнегреческих математиков, изучавших выпуклые фигуры. Однако формальное определение и систематическое исследование появились в XIX веке в рамках развития выпуклого анализа и геометрии. Важный вклад внесли Герман Минковский (теория выпуклых тел) и Константин Каратеодори (теорема Каратеодори, 1907 год). В XX веке, с развитием вычислительной геометрии, задача построения выпуклой оболочки стала одной из фундаментальных алгоритмических проблем.

¶Алгоритмы построения

Построение выпуклой оболочки для конечного множества точек — классическая задача вычислительной геометрии. Существует несколько основных алгоритмов, различающихся по сложности и применимости.

¶Алгоритм Джарвиса (заворачивание подарка)

Один из простейших алгоритмов. Начинается с самой левой (или самой нижней) точки. Затем последовательно выбирается точка, которая образует наименьший полярный угол с текущей точкой относительно предыдущего направления. Процесс продолжается, пока не будет достигнута начальная точка. Временная сложность: \(O(nh)\), где \(n\) — число точек, \(h\) — число точек на оболочке. В худшем случае (когда все точки лежат на оболочке) сложность \(O(n^2)\).

¶Алгоритм Грэхема

Более эффективный метод. Сначала находится точка с минимальной координатой \(y\) (или \(x\)). Затем все остальные точки сортируются по полярному углу относительно этой точки. После этого выполняется обход отсортированного списка с проверкой направления поворота (левое или правое). Точки, образующие правый поворот, удаляются. Временная сложность: \(O(n \log n)\) за счёт сортировки.

¶Алгоритм быстрой оболочки (Quickhull)

Рекурсивный алгоритм, аналогичный быстрой сортировке. Находит две крайние точки (например, с минимальной и максимальной \(x\)-координатой), которые заведомо принадлежат оболочке. Затем для каждой стороны рекурсивно ищется точка, максимально удалённая от прямой, образуемой этими точками. Точки, лежащие внутри треугольника, отбрасываются. Средняя сложность \(O(n \log n)\), в худшем случае \(O(n^2)\).

¶Алгоритм Эндрю (монотонные цепи)

Вариант алгоритма Грэхема, не требующий вычисления полярных углов. Точки сортируются по \(x\)-координате, а затем по \(y\)-координате. Строятся верхняя и нижняя части оболочки отдельно с помощью стеков. Временная сложность: \(O(n \log n)\).

¶Алгоритм Чана

Оптимальный алгоритм, работающий за \(O(n \log h)\). Комбинирует идеи алгоритмов Джарвиса и Грэхема. Разбивает точки на группы, строит их оболочки, а затем объединяет. Сложность зависит от \(h\), что делает его эффективным, когда точек на оболочке мало.

¶Применение

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

¶Вычислительная геометрия

• Коллизии и обнаружение столкновений: выпуклая оболочка используется как упрощённая модель объекта для быстрой проверки пересечений в компьютерной графике, робототехнике и физических симуляторах.
• Распознавание образов: построение минимальной выпуклой области, содержащей точки одного класса, для классификации.
• Визуализация данных: построение областей рассеяния на диаграммах.

¶Анализ данных и машинное обучение

• Опорные векторные машины (SVM): выпуклая оболочка обучающих выборок используется для нахождения разделяющей гиперплоскости.
• Кластеризация: выпуклая оболочка кластера позволяет визуализировать его форму и границы.

¶Геоинформационные системы (ГИС)

• Определение минимальной зоны покрытия: например, для расчёта зоны обслуживания вышки сотовой связи по набору точек.
• Анализ пространственного распределения: построение выпуклой оболочки для набора географических объектов (городов, станций).

¶Робототехника и планирование движения

• Построение карты препятствий: выпуклая оболочка используется для аппроксимации сложных препятствий в конфигурационном пространстве.
• Планирование пути: алгоритмы, основанные на выпуклых оболочках, позволяют находить кратчайшие пути в среде с препятствиями.

¶Экономика и теория игр

• Ядро кооперативной игры: выпуклая оболочка векторов выигрышей коалиций.
• Портфельный анализ: эффективная граница Марковица в теории инвестиций является выпуклой оболочкой множества возможных портфелей.

¶Обобщения и связанные понятия

• Выпуклая оболочка в пространствах большей размерности: для трёхмерного пространства существуют алгоритмы сложности \(O(n \log n)\) (например, алгоритм случайного инкрементального построения). Для размерности \(d > 3\) задача становится более сложной, и её сложность может достигать \(O(n^{\lfloor d/2 \rfloor})\).
• Аффинная оболочка: минимальное аффинное подпространство, содержащее множество. В отличие от выпуклой, не требует выпуклых комбинаций с неотрицательными коэффициентами.
• Выпуклая оболочка множества функций: в функциональном анализе — минимальная выпуклая функция, мажорирующая данное семейство функций.
• Выпуклая оболочка в метрических пространствах: понятие обобщается на произвольные метрические пространства, где выпуклая оболочка определяется через геодезические.

¶Интересные факты

• Теорема Каратеодори утверждает, что любая точка выпуклой оболочки множества \(S \subset \mathbb{R}^n\) может быть представлена как выпуклая комбинация не более чем \(n+1\) точки из \(S\).
• Теорема Радона (1921) гласит, что любое множество из \(n+2\) точек в \(\mathbb{R}^n\) можно разбить на два подмножества, выпуклые оболочки которых пересекаются.
• Задача построения выпуклой оболочки является одной из первых задач, для которых был разработан алгоритм с оптимальной сложностью \(O(n \log n)\) на плоскости (алгоритм Грэхема, 1972).
• В программировании выпуклая оболочка часто используется в задачах олимпиадного программирования и соревнований по алгоритмам.

¶Источники

• Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — М.: Мир, 1989.
• де Берг М., ван Кревелд М., Овермарс М., Шварцкопф О. Вычислительная геометрия. Алгоритмы и приложения. — М.: ДМК Пресс, 2016.
• Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973.
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. — 3rd ed. — MIT Press, 2009.