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

Выпуклой оболочкой множества [math]\displaystyle{ X }[/math] называется наименьшее выпуклое множество, содержащее [math]\displaystyle{ X }[/math]. «Наименьшее множество» здесь означает наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру.

Обычно выпуклая оболочка определяется для подмножеств векторного пространства над вещественными числами (в частности в евклидовом пространстве) и на соответствующих аффинных пространствах.

Выпуклая оболочка множества [math]\displaystyle{ X }[/math] обычно обозначается [math]\displaystyle{ \operatorname{Conv} X }[/math].

Пример

Выпуклая оболочка: пример с лассо

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

Свойства

• [math]\displaystyle{ X }[/math] — выпуклое множество тогда и только тогда, когда [math]\displaystyle{ \operatorname{Conv} X = X }[/math].
• Для произвольного подмножества линейного пространства [math]\displaystyle{ X }[/math] существует единственная выпуклая оболочка [math]\displaystyle{ \operatorname{Conv} X }[/math] — это пересечение всех выпуклых множеств, содержащих [math]\displaystyle{ X }[/math].
  • При этом

    [math]\displaystyle{ \operatorname{Conv} X = \bigcup_{n=1}^{\infty} ~\bigcup_{a_1,\dots,a_n \in X}~ \bigcup_{\lambda_1+\dots+\lambda_n=1} {\lambda_1 a_1+\dots+\lambda_n a_n},~ \lambda_i \ge 0 }[/math]

  • Более того, если размерность пространства равна [math]\displaystyle{ N }[/math] то верна следующая теорема Каратеодори:

    [math]\displaystyle{ \operatorname{Conv} X = \bigcup_{a_1,\dots,a_{N+1} \in X} \bigcup_{\lambda_1+\dots+\lambda_{N+1}=1} {\lambda_1 a_1+\dots+\lambda_{N+1} a_{N+1}},~ \lambda_i \ge 0 }[/math]

• Выпуклой оболочкой конечного набора точек на плоскости является выпуклый плоский многоугольник (в вырожденных случаях — отрезок или точка), причём его вершины являются подмножеством исходного набора точек. Аналогичный факт верен и для конечного набора точек во многомерном пространстве.
• Выпуклая оболочка [math]\displaystyle{ X }[/math] равна пересечению всех полупространств, содержащих [math]\displaystyle{ X }[/math].
• Теорема Крейна — Мильмана. Выпуклый компакт [math]\displaystyle{ K }[/math] в локально выпуклом пространстве [math]\displaystyle{ L }[/math] совпадает с замыканием выпуклой оболочки множества своих крайних точек [math]\displaystyle{ E(K) }[/math]

Вариации и обобщения

Выпуклой оболочкой функции f называют такую функцию [math]\displaystyle{ \operatorname{Conv} f }[/math], что

[math]\displaystyle{ \operatorname{epi}\; \operatorname{Conv} f = \operatorname{Conv}\; \operatorname{epi} f }[/math],

где epi f — надграфик функции f.

Стоит отметить связь понятия выпуклой оболочки функции с преобразованием Лежандра невыпуклых функций. Пусть f * — преобразование Лежандра функции f. Тогда если [math]\displaystyle{ \operatorname{Conv} f }[/math] —собственная функция (принимает конечные значения на непустом множестве), то

[math]\displaystyle{ f^{**} = \overline{\operatorname{Conv}} f }[/math]

[math]\displaystyle{ \overline{\operatorname{Conv}} f }[/math] — выпуклое замыкание f, то есть функция, надграфик которой является замыканием надграфика f.

Сложность построения

Из теоремы о верхней границе вытекает, что выпуклая оболочка множества из [math]\displaystyle{ n }[/math] точек в пространстве размерности [math]\displaystyle{ d }[/math] может быть построена алгоритмом сложности [math]\displaystyle{ O(n\log n) }[/math] для двумерного и трёхмерного случая и алгоритмом сложности [math]\displaystyle{ O(n^{\lfloor d/2\rfloor}) }[/math] в пространствах более высокой размерности.

См. также

• Алгоритм быстрой оболочки
• Алгоритм Грэхема
• Алгоритм Джарвиса
• Алгоритм Киркпатрика
• Алгоритм Чена
• Выпуклость
• Лемма Шепли — Фолкмана
• Метод эластичной сети

Литература

• Половинкин Е. С, Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: Физматлит, 2004. — 416 с. — ISBN 5-9221-0499-3.
• Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — С. 478.
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 33. Вычислительная геометрия // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4.
• Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. — С. 304.
• Шаблон:Source
• Г. Г. Магарил-Ильяев, В. М. Тихомиров. Выпуклый анализ и его приложения. Изд. 2-е, исправл. —М.: Едиториал УРСС. 2003. —176 с. —ISBN 5-354-0262-1.