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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Пример

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

Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю (лассо) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. В таком положении петля и окружённая ей область доски являются выпуклой оболочкой для всей группы гвоздей<ref>Даниэль Хэльпер, курс «Построение алгоритмов», Хайфский университет.</ref>.

Свойства

  • <math>X</math> — выпуклое множество тогда и только тогда, когда <math>\operatorname{Conv} X = X</math>.
  • Для произвольного подмножества линейного пространства <math>X</math> существует единственная выпуклая оболочка <math>\operatorname{Conv} X</math> — это пересечение всех выпуклых множеств, содержащих <math>X</math>.
    • При этом
      <math>\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>N</math> то верна следующая теорема Каратеодори:
      <math>\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>X</math> равна пересечению всех полупространств, содержащих <math>X</math>.
  • Теорема Крейна — Мильмана. Выпуклый компакт <math>K</math> в локально выпуклом пространстве <math>L</math> совпадает с замыканием выпуклой оболочки множества своих крайних точек <math>E(K)</math>

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

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

<math>\operatorname{epi}\; \operatorname{Conv} f = \operatorname{Conv}\; \operatorname{epi} f</math>,

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

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

<math>f^{**} = \overline{\operatorname{Conv}} f</math>


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

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

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

См. также

Шаблон:Кол

Шаблон:Кол

Примечания

Шаблон:Примечания

Литература

Источник — https://camokathomelab.servebeer.com/mediawiki/index.php?title=Выпуклая_оболочка&oldid=31860