Прямий кістяк

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

Процес усадки, прямий кістяк (синім) та модель даху.

Перше визначення прямого кістяка для простих многокутників було розроблено в 1996 році^[1] та узагальнено для планарних прямолінійних графів.^[2] Інтерпретація задачі, як проєкція поверхонь дахів, широко обговорювалась Ґ. А. Пешкою.^[3]

Означення

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

Алгоритми

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

• Айшхользер^[1][2] показав як вичислити прямий кістяк для довільного двомірного многокутника за час O(n³ log n)^[4], або, більш точно, за час O((n²+f) log n), де n — кількість вершин, а f — число перетинів вершин із несуміжними сторонами під час будування. Найкраще відома оцінка для f — O(n³).
• Алгоритм з найгіршим часом O(nr log n), або простіше O(n² log n), був запропонований Губером та Гелдом, які аргументували, що їх підхід працюватиме майже за лінійний час для більшості випадків.^[5][6]
• Петр Фелькер та Степан Обджалек розробили алгоритм, що відомий оцінкою O(nr + n log r). Проте, відомо, що їх алгоритм є неправильним.^[7][8]
• Використовуючи структури для задачі найближчої пари точок, Епштейн та Еріксон показали, як побудувати прямий кістяк, використовуючи лінійне число оновлень структури даних задачі найближчої пари. Алгоритм структури найближчої пари базується на дереві квадрантів та передбачає оцінку часу O(nr + n log n), чи з істотно більш складною структурою даних, що забезпечує кращу оцінку асимптотики O(n^{1 + ε} + n^{8/11 + ε}r^{9/11 + ε}), де ε — будь-яка константа більша за нуль.^[9] Цей алгоритм залишається найкращим за оцінкою для прямого кістяку без умов на вхідні дані, але він складний і ще не був реалізований.
• Для простих многокутників, задача побудови прямого кістяка простіша. Ченґ на Віґнерон показали як вичислити прямий кістяк для простих многокутників з n вершинами, r з яких мають кути більші ніж Пі, за час O(n log² n + r^3/2 log r).^[10] В найкращому випадку r може бути лінійною, тоді оцінка часу може бути спрощена до O(n^3/2 log n).
• Монотонний многокутник по відношенню до L — це многокутник зі властивістю, що кожна лінія перпендикулярна до L перетинає многокутник в одинарному інтервалі. Коли вхідний многокутник є монотонним, його прямий кістяк може бути побудований за час O(n log n).^[11]

Використання

Кожна точка всередині вхідного многокутника може бути піднята у тривимірний простір з використанням того часу, за який процес стиснення досягає цієї точки, як координату z. В результаті, тривимірна площина має постійну висоту на границі многокутника, та піднімається з постійним кутом по відношенню до них, крім точок самого прямого кістяка, де частини площини з'єднуються під різними кутами. Таким чином, прямий кістяк може бути використаний як множина ребер для будівництва даху, розміщений на стінах у формі початкового многокутника.^[1][12] Найнижча фігура на ілюстрації показує площину, побудовану з прямого кістяка цим способом.

Демаін та Лубів використовували прямий кістяк як частину техніки для складання листа паперу таким чином, що даний многокутник може бути розрізаний одним прямим розрізом (теорема оригамі про вирізання многокутника), та пов'язана з проблемами проектування оригамі.^[13]

Бареквет, використовує прямий кістяк в алгоритмі для знаходження тривимірної площини, що інтерполює між двома даними ламаними.^[14]

Танас та Велткамп пропонують розкласти неопуклі многокутники на об'єднання опуклих зон, використовуючи прямий кістяк, при зіставленні форм у обробці зображень як крок попередньої обробки.^[15]

Баджері та Раззарі використовують прямий кістяк, щоб показати укладку вершин у алгоритмі візуалізації графу, де малюнок графу обмежений границею многокутника.^[16]

Прямий кістяк може також бути використаний для побудови паралельної кривої многокутника, аналогічний до побудови паралельної кривої з закругленими кутами утворених від серединної осі. Томоеда та Суґіхара застосували цю ідею до розробки вивіски, яку видно з ширших кутів, з ілюзією видимості глибини.^[17] Точно так же, Ацент та Карр використовують прямі кістяки для розробки кольорових градієнтів, що відповідають контурам літер чи іншим фігурам.^[18]

Разом з іншими типами кістяків, таких як медіальна вісь, прямий кістяк може бути використаний для згортання двомірної області до спрощеного одномірного представлення. Наприклад, Ганерт та Сестер описують використання цього типа прямого кістяка в географічних інформаційних системах для знаходження осьових ліній доріг.^[19]

Кожне дерево без жодної вершини другої степені може бути реалізовано як прямий кістяк опуклого многокутника.^[20] Опукла оболонка площини даху співвідноситься з його прямим кістяком, формуючи реалізацію Штайніца графу Халіна, сформований з дерева приєднанням його листків у циклі.

Більші виміри

Бареквет описав версію прямого кістяка для тривимірного многогранника, алгоритм для його обчислення та проаналізував його складність для декількох видів многогранників.^[21]

Губер досліджував метричні простори в яких відповідні діаграми Вороного та прямі кістяки збігаються. Для двох вимірів, характеристика таких метричних вимірів завершена. Для більших вимірів, цей метод може бути інтерпретований як узагальнення прямих кістяків для певних вхідних фігур для довільних вимірів за допомогою діаграм Вороного.^[22]