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

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

В математиці, опукла оболонка для множини точок X дійсному векторному просторі V це мінімальна опукла множина, що містить 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 \ge 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 \ge 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.