Складність уявлення опуклої оболонки

Випуклі оболонки у тривимірному просторі використовуються у різних додатках. Наприклад, вони використовуються для прискорення знаходження колізій у комп'ютерній анімації. Припустимо, ми хочемо перевірити, чи перетинаються два об'єкти

і. Якщо здебільшого об'єкти не перетинаються, наступна стратегія дає выигрыш. Апроксимуємо об'єкт простішими об'єктамиівідповідно, які містять у собі вихідні об'єкти. Якщо ми хочемо перевірити, чи перетинаютьсяі, то спочатку слід перевірити, чи перетинаютьсяі. Тільки якщоіперетинаються, необхідно перевірити перетинаються вихідні об'єкти.

Апроксимація об'єкта обмежувальною сферою та опуклою оболонкою

У разі сфер, що обмежують, перевірка перетину сфер досить проста, але для багатьох об'єктів сфери не дають хорошої апроксимації. При використанні опуклих оболонок перевірка перетину складніша, ніж для сфер, але більшість об'єктів краще апроксимуються.

Побудова опуклої оболонки є одним із центральних завдань для математики та обчислювальної геометрії.

Складність уявлення опуклої оболонки

Нагадаємо [1], що у двовимірному випадку опукла оболонка представляє впорядковану послідовність вершин. Дане раніше визначення опуклої оболонки також поширюється і тривимірний випадок.

Випукла оболонка множини точок у тривимірному просторі є опуклим багатогранником, вершини якого належать вихідній множині точок. Синоніми: політоп, поліедр.Граньюопуклого багатогранника є максимальне підмножина копланарних точок (крапок, що лежать в одній площині) на його межі. Зауважимо, грань є опуклим багатокутником.Ребромопуклого

Як і двомірному випадку, у тривимірному проблеми, пов'язані з поданням, також дуже серйозні. Багатогранник може бути повністю визначений перерахуванням його вершин, ребер та граней.

Як відомо [2], для зв'язкових планарних графів з

вершинами,ребрами ігранями справедлива формула Ейлера:, а оскільки межа опуклого політопа є планарним графом - див. малюнок 3, то співвідношення Ейлер справедливо і для кількості вершин, ребер і граней опуклого багатогранника.

Перетворення куба в планарний графік. Одна з граней перетворюється на необмежену область планарного графа

Виходячи з того, що кожна грань і вершина багатогранника має принаймні три інцидентні ребра, отримаємо такі нерівності:

,

які показують, що

,іпопарно пропорційні. Звідси випливає, що для повного опису (подання) багатогранника звершинами достатньо обсягу пам'яті. Понад те, спираючись те що, що скелет багатогранника є планарним графом, багатогранник може бути представлений, використовуючи будь-яку структуру даних, придатну для представлення планарного графа (такі як списки суміжності чи реберний список з подвійними зв'язками [3]). Якщо опуклий політоп єсимпліціальним(у тривимірному просторі це означає, що кожна грань є трикутником), всі наведені вище нерівності перетворюються на рівності.

Після того, як встановлена ​​складність уявлення опуклої оболонки, природно поставити питання, яка нижня оцінка складність побудови опуклої оболонки в тривимірному просторі? З одного боку, оскільки будь-яка сукупність точок у двовимірному просторі тривіальним чином вкладається втривимірний простір, то нижня оцінка складності побудови опуклої оболонки у тривимірному просторі дорівнює

. З іншого, нижче буде пред'явлено алгоритм, що досягає нижньої оцінки. Розглянемо основні алгоритми побудови опуклої оболонки.

---