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

В роботі розглядається ряд задач на побудову і підрахунок множини простих многокутників різних типів, вершинами яких є всі точки заданої скінченої множини точок і які задовольняють певним критеріям. Для аналізу вхідної множини точок і побудови простих многокутників введені діаграма еквівалентності зіркових розбиттів і граф взаємної видимості вільних точок. Досліджено їх властивості. Для вирішення задачі побудови, підрахунку множини усіх простих многокутників і породження випадкових многокутників на цій множині використано метод послідовного нарощування простого ланцюга з відсіканням. Непродуктивні гілки дерева варіантів відсікаються за допомогою аналізу структури графа взаємної видимості вільних точок, що представляє собою геометричний граф. Розширено перелік необхідних і достатніх умов існування Гамільтона шляху в таких графах, як на основі аналізу їх зв'язності, так і з використанням специфічних умов побудови простого многокутника. Для аналізу гамільтоновості графа, у тому числі, використані двозв'язні компоненти і точки сполучення. Сформульовано і доведено ряд тверджень, що дозволяють прорідити граф взаємної видимості вільних точок, зменшуючи при цьому дерево варіантів. Запропонований підхід дозволяє збільшити максимальний розмір вхідної множини точок для точного повного рішення в середньому з 15 до 25-30 в залежності від конфігурації точок. Крім того, використання графа взаємної видимості вільних точок дозволяє отримувати точне рішення для важливого окремого випадку - побудови простих многокутників при заданих областях, які заборонено перетинати ребрами многокутника.