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

Афінною оболонкою відрізка є пряма, афінною оболонкою плоского многокутника є площина.

Означення. Нехай в Ed задано k різних точок p1, p2, ...,pk. Множина точок p таких що

p = a1p1 + a2p2 + ... + akpk (ai R, ai 0, a1 + a2 + ...+ ak = 1)

називається опуклою множиною, породженою точками p1, p2, ..., pk, а p називається опуклою комбінацією точок p1, p2, ..., pk.

Опукла комбінація є звуженням афінної комбінації. При k = 2 опуклою множиною є відрізок, який сполучає задані точки.

Означення. Нехай в просторі Ed задана підмножина L. Опуклою оболонкою conv(L) множини L називається найменша опукла множина, яка містить L.

Означення. Поліедральною множиною в називається перетин скінченної множини замкнених півпросторів (півпростір – це частина Ed, розташована по одну сторону від деякої гіперплощини).

Поліедральна множина є опуклою, оскільки півпростір є опуклим та перетин опуклих множин є опуклою множиною. Плоскі многокутники та тривимірні многогранники є прикладами скінченних поліедральних множин. Скінченну d - мірну поліедральну множину будемо називати опуклим d - політопом (або просто політопом).

Теорема. Опукла оболонка скінченної множини точок в є опуклим політопом. Кожний опуклий політоп є опуклою оболонкою деякої скінченної множини точок.

Опуклий політоп задається описом його границі, яка складається з граней. Кожна грань опуклого політопа є опуклою множиною (політопом низької розмірності). Якщо політом має вимірність d, то його d - 1 грані називаються гіпергранями, d - 2 грані – підгранями, 1 - грані – ребрами, 0 - грані – вершинами. Для 3 політопа гіпергранями є плоскі многокутники, а підграні та ребра співпадають. В цій термінології порожня множина трактується як (-1) грань.

Означення. d політоп називається d симплексом, якщо він є опуклою оболонкою (d + 1) афінно незалежних точок. Кожна підмножина з цих d вершин є симплексом і є гранню. Кожна k грань містить 2k+1 граней розмірностей k, k-1, k-2, ..., 0, -1.

При d = 0, 1, 2, 3 відповідний симплекс є точкою, ребром, трикутником та трикутною пірамідою.Наприклад, трикутна піраміда (3 грань) містить одну 3 грань (сама піраміда), чотири 2 грані (трикутники), шість 1 граней (ребра), чотири 0 граней (вершини) та одну (-1) грань (порожня множина), що разом складає 16 = 24 граней.

Означення. d політоп називається симпліциальним, якщо його кожна гіпергрань є симплексом.

Задача 1. Опукла оболонка. В Ed задано множину S, що містить N точок. Необхідно побудувати їх опуклу оболонку (повний опис границі CH(S)).

Задача 2. Крайні точки. В Ed задано множину S, що містить N точок. Необхідно визначити ті з них, які є вершинами опуклої оболонки conv(S).

Задача 3. Перевірка крайності точок площини. На площині задано N точок. Визначити, чи є вони вершинами своєї власної опуклої оболонки.

Теорема. Задача сортування зводиться за лінійний час до задачі побудови опуклої оболонки. Для знаходження впорядкованих N точок опуклої оболонки потрібен час O(N log N).

Доведення. Нехай дано N додатних дійсних чисел x1, x2, ..., xN. Поставимо у відповідність точці xi точку (xi, xi+1) і присвоємо їй номер i. Утворені точки лежать на параболі y = x2. Опукла оболонка цієї множини точок буде складатися зі списку точок множини, впорядкованому за значенням абсциси.

Означення. Точка p опуклої множини S називається крайньою, якщо не існує пари точок a, b S таких, що лежить на відкритому відрізку ab.