WikiSort.ru - Не сортированное

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

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

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

Пример

Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю (лассо) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. Те гвозди, которых она касается, составляют выпуклую оболочку для всей группы гвоздей^[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}$ .

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

Выпуклой оболочкой функции 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.

См. также

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

Литература

• Половинкин Е. С, Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: Физматлит, 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.
• Левитин А. В. Глава 3. Метод грубой силы: Поиск выпуклой оболочки // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 157. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>

Примечания

Это заготовка статьи по геометрии. Вы можете помочь проекту, дополнив её.