Пошук академічних текстів

Інформація × Реєстраційний номер 0416U005100, Кандидатська дисертація На здобуття к.ф.-м.н. Дата захисту 30-06-2016 Статус Запланована Назва роботи Побудова генератора геометричних об'єктів із заданими властивостями на площині. Здобувач Фісуненко Андрій Леонідович, Керівник Терещенко Василь Миколайович Опонент Семенова Наталія Володимирівна Опонент Рисцов Ігор Костянтинович Опис В роботі розглядається ряд задач на побудову і підрахунок множини простих многокутників різних типів, вершинами яких є всі точки заданої скінченої множини точок і які задовольняють певним критеріям. Для аналізу вхідної множини точок і побудови простих многокутників введені діаграма еквівалентності зіркових розбиттів і граф взаємної видимості вільних точок. Досліджено їх властивості. Для вирішення задачі побудови, підрахунку множини усіх простих многокутників і породження випадкових многокутників на цій множині використано метод послідовного нарощування простого ланцюга з відсіканням. Непродуктивні гілки дерева варіантів відсікаються за допомогою аналізу структури графа взаємної видимості вільних точок, що представляє собою геометричний граф. Розширено перелік необхідних і достатніх умов існування Гамільтона шляху в таких графах, як на основі аналізу їх зв'язності, так і з використанням специфічних умов побудови простого многокутника. Для аналізу гамільтоновості графа, у тому числі, використані двозв'язні компоненти і точки сполучення. Сформульовано і доведено ряд тверджень, що дозволяють прорідити граф взаємної видимості вільних точок, зменшуючи при цьому дерево варіантів. Запропонований підхід дозволяє збільшити максимальний розмір вхідної множини точок для точного повного рішення в середньому з 15 до 25-30 в залежності від конфігурації точок. Крім того, використання графа взаємної видимості вільних точок дозволяє отримувати точне рішення для важливого окремого випадку - побудови простих многокутників при заданих областях, які заборонено перетинати ребрами многокутника. Дата реєстрації 2016-06-30 Додано в НРАТ 2020-04-03 Закрити