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

• Фісуненко Андрій Леонідович (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"