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

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

Опукла оболонка: аналог еластичної пов'язки

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

Властивості

• $X$ — опукла множина тоді і тільки тоді, коли $\operatorname {Conv} X=X$.
• Для довільної підмножини лінійного простору $X$ існує єдина опукла оболонка $\operatorname {Conv} X$ — перетин усіх опуклих множин, що містять $X$.
  • При цьому

    $\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$

  • Більш того, якщо вимірність простору дорівнює $N$ тоді вірна наступна теорема Каратеодорі про опуклу оболонку:

    $\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$

• Опуклою оболонкою скінченного набору точок на площині є опуклий плоский багатокутник (у вироджених випадках — відрізок або точка), причому його вершини є підмножиною похідного набору точок. Аналогічний факт вірний і для скінченного набору точок в багатовимірному просторі.
• Опукла оболонка $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.

Способи побудови

• Алгоритми обчислення опуклої оболонки
• Задача динамічної підтримки опуклої оболонки

Див. також

• Опукла поверхня
• Ортогональна опукла оболонка
• Лема Шеплі — Фолкмана
• Опуклий аналіз
• Теорема Тверберга

Посилання

• Weisstein, Eric W. Convex Hull(англ.) на сайті Wolfram MathWorld.
• «Convex Hull» by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.