Побудова генератора геометричних об’єктів із заданими властивостями на площині

Головним результатом дисертаційної роботи є побудова мультиалгоритмічної платформи-генератора геометричних об’єктів на площині, що розв’язує задачу породження простих многокутників певних типів із визначеними властивостями на заданих скінчених множинах точок. Основні результати дисертації.
1. Вперше застосовано поняття діаграми еквівалентності зіркових розбиттів, та областей еквівалентності для аналізу вхідних множин точок на площині та процедур породження декількох типів простих многокутників.
2. Досліджено та суттєво розширено перелік необхідних і достатніх умов існування Гамільтонового шляху в таких геометричних графах і відповідно, перевірки можливості завершити ланцюг побудовою простого многокутника. Умови існування Гамільтонового шляху базуються на аналізі графу взаємної видимості вільних точок. Загальна складність усіх перевірок умов обмежена O(N 2 ) при умові використання
O(N 2 ) пам’яті. Отримано прискорення алгоритму шляхом скорочення об’єму обчислювань з плаваючою точкою на перевірки перетинів відрізків ціною O(N 4 ) пам’яті, в якій зберігається попередньо оброблена інформація про перетині усіх пар відрізків.
3. Розроблено метод послідовного нарощування простого ланцюга з відсіканням дерева варіантів для реалістичних розмірів вхідної множини, який, фактично, наблизив складність обчислювань до O(P(N)a N ), де P(N) – поліноміальна функція від N; а – деяка константа.
4. Розроблено метод підрахунку усіх можливих простих многокутників на заданій скінченій множині точок, який суттєво прискорює процедури шляхом рекурсивного розбиття на під-задачі пошуку кількості Гамільтонових шляхів на двозв’язних компонентах та перемноження окремих результатів.
5. Розроблено евристичний метод породження простих многокутників нарощуванням простих оболонок на видаленому ребрі простого ланцюга, що будується. Доведено, що метод є одним із самих ефективних на сьогодні, маючи часову складність O(NlogN), та потребуючи O(N) пам’яті. Показано, що деякі з відомих типів простих многокутників, зокрема спіральні, можуть бути отримані, як окремий випадок запропонованого методу.
6. Узагальнено метод нарощування простих оболонок для евклідових просторів довільної розмірності. 7. Доведено існування простого поліедру для скінченої множини точок у, так званому, загальному розташуванні, коли жодна з d+1 точок не знаходяться в одній гіперплощині.

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

Фісуненко А. Л. Побудова генератора геометричних об’єктів із заданими властивостями на площині : дис. ... канд. фіз-мат. наук : 01.05.01 теоретичні основи інформатики та кібернетики / Фісуненко Андрій Леонідович - Київ, 2016. - 129 с.