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

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

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

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

Выпуклая оболочка множества обычно обозначается .

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

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

  •  — выпуклое множество тогда и только тогда, когда .
  • Для произвольного подмножества линейного пространства существует единственная выпуклая оболочка  — это пересечение всех выпуклых множеств, содержащих .
    • При этом
    • Более того, если размерность пространства равна то верна следующая теорема Каратеодори:
  • Выпуклой оболочкой конечного набора точек на плоскости является выпуклый плоский многоугольник (в вырожденных случаях — отрезок или точка), причём его вершины являются подмножеством исходного набора точек. Аналогичный факт верен и для конечного набора точек во многомерном пространстве.
  • Выпуклая оболочка равна пересечению всех полупространств, содержащих .
  • Теорема Крейна — Мильмана. Выпуклый компакт в локально выпуклом пространстве совпадает с замыканием выпуклой оболочки множества своих крайних точек

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

[править | править код]

Выпуклой оболочкой функции f называют такую функцию , что

,

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

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


 — выпуклое замыкание f, то есть функция, надграфик которой является замыканием надграфика f.

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

[править | править код]

Из теоремы о верхней границе вытекает, что выпуклая оболочка множества из точек в пространстве размерности может быть построена алгоритмом сложности для двумерного и трёхмерного случая и алгоритмом сложности в пространствах более высокой размерности.[2] [3]

Литература

[править | править код]
  • Половинкин Е. С, Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: Физматлит, 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
  • Г. Г. Магарил-Ильяев, В. М. Тихомиров. Выпуклый анализ и его приложения. Изд. 2-е, исправл. М.: Едиториал УРСС. 2003. 176 с. ISBN 5-354-0262-1.

Примечания

[править | править код]
  1. Даниэль Хэльпер, курс «Построение алгоритмов», Хайфский университет.
  2. 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
  3. de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008), Computational Geometry: Algorithms and Applications (3rd ed.), Springer