Search academic texts

Information × Registration Number 0416U005100, Candidate dissertation Status к.ф.-м.н. Date 30-06-2016 popup.evolution o Title Constructing a generator of geometric objects with defined properties on the plain. Author Fisunenko Andriy Leonidovych, popup.head Tereshchenko Vasyl Mykolayovych popup.opponent Семенова Наталія Володимирівна popup.opponent Рисцов Ігор Костянтинович Description В роботі розглядається ряд задач на побудову і підрахунок множини простих многокутників різних типів, вершинами яких є всі точки заданої скінченої множини точок і які задовольняють певним критеріям. Для аналізу вхідної множини точок і побудови простих многокутників введені діаграма еквівалентності зіркових розбиттів і граф взаємної видимості вільних точок. Досліджено їх властивості. Для вирішення задачі побудови, підрахунку множини усіх простих многокутників і породження випадкових многокутників на цій множині використано метод послідовного нарощування простого ланцюга з відсіканням. Непродуктивні гілки дерева варіантів відсікаються за допомогою аналізу структури графа взаємної видимості вільних точок, що представляє собою геометричний граф. Розширено перелік необхідних і достатніх умов існування Гамільтона шляху в таких графах, як на основі аналізу їх зв'язності, так і з використанням специфічних умов побудови простого многокутника. Для аналізу гамільтоновості графа, у тому числі, використані двозв'язні компоненти і точки сполучення. Сформульовано і доведено ряд тверджень, що дозволяють прорідити граф взаємної видимості вільних точок, зменшуючи при цьому дерево варіантів. Запропонований підхід дозволяє збільшити максимальний розмір вхідної множини точок для точного повного рішення в середньому з 15 до 25-30 в залежності від конфігурації точок. Крім того, використання графа взаємної видимості вільних точок дозволяє отримувати точне рішення для важливого окремого випадку - побудови простих многокутників при заданих областях, які заборонено перетинати ребрами многокутника. Registration Date 2016-06-30 popup.nrat_date 2020-04-03 Close