Меню Главная Случайная статья Настройки Выпуклая оболочка Материал из https://ru.wikipedia.org Выпуклой оболочкой множества ${\displaystyle X}$ называется наименьшее выпуклое множество, содержащее ${\displaystyle X}$. «Наименьшее множество» здесь означает наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру. Обычно выпуклая оболочка определяется для подмножеств векторного пространства над вещественными числами (в частности в евклидовом пространстве) и на соответствующих аффинных пространствах. Выпуклая оболочка множества ${\displaystyle X}$ обычно обозначается ${\displaystyle \operatorname {Conv} X}$. Содержание 1 Пример 2 Свойства 3 Вариации и обобщения 4 Сложность построения 5 См. также 6 Примечания 7 Литература Пример Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю (лассо) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. В таком положении петля и окружённая ей область доски являются выпуклой оболочкой для всей группы гвоздей[1]. Свойства ${\displaystyle X}$ — выпуклое множество тогда и только тогда, когда ${\displaystyle \operatorname {Conv} X=X}$. Для произвольного подмножества линейного пространства ${\displaystyle X}$ существует единственная выпуклая оболочка ${\displaystyle \operatorname {Conv} X}$ — это пересечение всех выпуклых множеств, содержащих ${\displaystyle X}$. При этом ${\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}\geq 0}$ Более того, если размерность пространства равна ${\displaystyle N}$ то верна следующая теорема Каратеодори: ${\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}\geq 0}$ Выпуклой оболочкой конечного набора точек на плоскости является выпуклый плоский многоугольник (в вырожденных случаях — отрезок или точка), причём его вершины являются подмножеством исходного набора точек. Аналогичный факт верен и для конечного набора точек во многомерном пространстве. Выпуклая оболочка ${\displaystyle X}$ равна пересечению всех полупространств, содержащих ${\displaystyle X}$. Теорема Крейна — Мильмана. Выпуклый компакт ${\displaystyle K}$ в локально выпуклом пространстве ${\displaystyle L}$ совпадает с замыканием выпуклой оболочки множества своих крайних точек ${\displaystyle E(K)}$ Вариации и обобщения Выпуклой оболочкой функции f называют такую функцию ${\displaystyle \operatorname {Conv} f}$, что ${\displaystyle \operatorname {epi} \;\operatorname {Conv} f=\operatorname {Conv} \;\operatorname {epi} f}$, где epi f — надграфик функции f. Стоит отметить связь понятия выпуклой оболочки функции с преобразованием Лежандра невыпуклых функций. Пусть f * — преобразование Лежандра функции f. Тогда если ${\displaystyle \operatorname {Conv} f}$ —собственная функция (принимает конечные значения на непустом множестве), то ${\displaystyle f^{**}={\overline {\operatorname {Conv} }}f}$ ${\displaystyle {\overline {\operatorname {Conv} }}f}$ — выпуклое замыкание f, то есть функция, надграфик которой является замыканием надграфика f. Сложность построения Из теоремы о верхней границе вытекает, что выпуклая оболочка множества из ${\displaystyle n}$ точек в пространстве размерности ${\displaystyle d}$ может быть построена алгоритмом сложности ${\displaystyle O(n\log n)}$ для двумерного и трёхмерного случая и алгоритмом сложности ${\displaystyle O(n^{\lfloor d/2\rfloor })}$ в пространствах более высокой размерности.[2] [3] См. также Алгоритм быстрой оболочки Алгоритм Грэхема Алгоритм Джарвиса Алгоритм Киркпатрика Алгоритм Чена Выпуклость Лемма Шепли — Фолкмана Метод эластичной сети Примечания Даниэль Хэльпер, курс «Построение алгоритмов», Хайфский университет. Chazelle, Bernard (1985), On the convex layers of a planar set, IEEE Transactions on Information Theory, 31 (4): 509–517, doi:10.1109/TIT.1985.1057060, MR 0798557 Литература Половинкин Е. С, Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: Физматлит, 2004. — 416 с. — ISBN 5-9221-0499-3. Левитин А. В. Глава 3. Метод грубой силы: Поиск выпуклой оболочки // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 157. — 576 с. — ISBN 978-5-8459-0987-9 Г. Г. Магарил-Ильяев, В. М. Тихомиров. Выпуклый анализ и его приложения. Изд. 2-е, исправл. —М.: Едиториал УРСС. 2003. —176 с. —ISBN 5-354-0262-1.