imported>Matsievsky: /* Литература */

2025-06-05T09:29:50Z

Литература

Новая страница

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

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

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

== Пример ==
[[Image:ConvexHull.svg|thumb|Выпуклая оболочка: пример с лассо]]

Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю ([[лассо]]) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. В таком положении петля и окружённая ей область доски являются ''выпуклой оболочкой'' для всей группы гвоздей<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
| last = Chazelle | first = Bernard | author-link = Bernard Chazelle
| doi = 10.1109/TIT.1985.1057060
| issue = 4
| journal = [[IEEE Transactions on Information Theory]]
| mr = 798557
| pages = 509–517
| title = On the convex layers of a planar set
| volume = 31
| year = 1985}} </ref>
<ref>{{citation
| last1 = de Berg | first1 = M. | author1-link = Mark de Berg
| last2 = van Kreveld | first2 = M. | author2-link = Marc van Kreveld
| last3 = Overmars | first3 = Mark | author3-link = Mark Overmars
| last4 = Schwarzkopf | first4 = O. | author4-link = Otfried Cheong
| edition = 3rd
| publisher = Springer
| title = Computational Geometry: Algorithms and Applications
| year = 2008}}
*{{citation
| last = Chan | first = Timothy M. | author-link = Timothy M. Chan
| doi = 10.1142/S0218195912600096
| issue = 4
| journal = [[International Journal of Computational Geometry and Applications]]
| mr = 2994585
| pages = 341–364
| title = Three problems about dynamic convex hulls
| volume = 22
| year = 2012}}</ref>

== См. также ==
{{кол}}
* [[Алгоритм быстрой оболочки]]
* [[Алгоритм Грэхема]]
* [[Алгоритм Джарвиса]]
* [[Алгоритм Киркпатрика]]
* [[Алгоритм Чена]]
* [[Выпуклое множество|Выпуклость]]
* [[Лемма Шепли — Фолкмана]]
* [[Метод эластичной сети]]
{{кол|конец}}

== Примечания ==
{{примечания}}

== Литература ==
* ''Половинкин Е. С, Балашов М. В.'' Элементы выпуклого и сильно выпуклого анализа. — {{М}}: Физматлит, 2004. — 416 с. — ISBN 5-9221-0499-3.
* {{книга
|автор = Прапарата Ф., Шеймос М.
|заглавие = Вычислительная геометрия: Введение
|оригинал = Computational Geometry An introduction
|издательство = Мир
|место = М.
|год = 1989
|страницы = 478
}}
* {{книга
|часть = '''Глава 33. Вычислительная геометрия'''
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|автор = Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд.
|ссылка = https://archive.org/details/introductiontoal0000unse_h3k5
|издание = 2-e издание
|isbn = 5-8459-0857-4
|страницы =
|год = 2005
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}
* {{книга
|автор = Ласло М.
|заглавие = Вычислительная геометрия и компьютерная графика на C++
|издательство = БИНОМ
|место = М.
|год = 1997
|страницы = 304
}}
* {{source|Q21694522|part=Глава 3. Метод грубой силы: Поиск выпуклой оболочки|pages=157}}
* [[Магарил-Ильяев, Георгий Георгиевич|Г. Г. Магарил-Ильяев]], В. М. Тихомиров. Выпуклый анализ и его приложения. Изд. 2-е, исправл. [[Лемма Шепли — Фолкмана|—]]М.: Едиториал УРСС. 2003. [[Лемма Шепли — Фолкмана|—]]176 с. [[Лемма Шепли — Фолкмана|—]]ISBN 5-354-0262-1.

[[Категория:Выпуклая геометрия]]
[[Категория:Выпуклые оболочки]]
[[Категория:Выпуклый анализ]]

Выпуклая оболочка - История изменений

imported>Matsievsky: /* Литература */