Опукла оболонка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Опукла оболонка: аналог еластичної пов'язки

Опукла оболонка (англ. Convex hull) множини точок X на евклідовій площині або у просторі — це мінімальна опукла множина, що містить X.

В обчислювальній геометрії, прийнято використовувати термін «опукла оболонка» для границі мінімальної опуклої множини, що містить дану не порожню скінченну множину точок на площині. Для скінченної множини точок, опукла оболонка являє собою ламану лінію.

Властивості[ред.ред. код]

  • X — опукла множина тоді і тільки тоді, коли \operatorname{Conv} X=X.
  • Для довільної підмножини лінійного простору X існує єдина опукла оболонка \operatorname{Conv} X — перетин усіх опуклих множин, що містять X.
  • Опуклою оболонкою скінченного набору точок на площині є опуклий плаский багатокутник (у вироджених випадках — відрізок або точка), причому його вершини є підмножиною похідного набору точок. Аналогічний факт вірний і для скінченного набору точок в багатовимірному просторі.
  • Опукла оболонка X дорівнює перетину всіх півпросторів, що містять X.
  • Для двох опуклих множин, які не перетинаються, завжди існує гіперплощина, що їх розділяє.

Варіації і узагальнення[ред.ред. код]

Опуклою оболонкою функції f називають таку функцію \operatorname{Conv} f, що

\operatorname{epi}\; \operatorname{Conv} f = \operatorname{Conv}\; \operatorname{epi} f,

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

Варто зауважити зв'язок поняття опуклої оболонки функції з перетворенням Лежандра неопуклих функцій. Нехай f * — перетворення Лежандра функції f. Тоді якщо \operatorname{Conv} f — власна функція (приймає скінченні значення на непорожньой множині), тоді

f^{**} = \overline{\operatorname{Conv}} f


\overline{\operatorname{Conv}} f — опукле замкнення f, тобто існує функція, надграфік якої є замкненням надграфіка f.

Способи побудови[ред.ред. код]

Див. також[ред.ред. код]

Посилання[ред.ред. код]