Москва, г. Москва и Московская область, Россия
Россия
В данной статье осуществляется поиск алгоритма рекомбинации β-ребер для алгоритма образования αβ-триангуляции из произвольной триангуляции на евклидовой плоскости. Выявлены возможные нарушения структуры . Определена асимптотическая временная сложность алгоритма.
триангуляция, αβ-триангуляция, свойства αβ-триангуляции, алгоритм оптимизации, рекомбинация ребер
1. Лебединская Н.А. Преобразование триангуляций при помощи элементарных операций [Текст] / Н.А. Лебединская, Д.М. Лебединский // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. – 2009. – № 1. – С. 84-86. EDN: https://elibrary.ru/KVNEAB
2. Рустамян В.В. Анализ топологии полиэдров в задаче аппроксимации замкнутых поверхностей полиэдрами с группами конгруэнтных граней [Текст] / В.В. Рустамян // GraphiCon 2024: Материалы 34-й Международной конференции по компьютерной графике и машинному зрению, Омск, 17–19 сентября 2024 года. – Омск: Омский государственный технический университет, 2024. – С. 827-836. – DOIhttps://doi.org/10.25206/978-5-8149-3873-2-2024-827-836. EDN: https://elibrary.ru/DLSJMT
3. Рустамян В.В. Анализ основных параметров генетического алгоритма при решении задачи аппроксимации замкнутых поверхностей свободной формы полиэдрами с группами конгруэнтных треугольников [Текст] / В.В. Рустамян // Геометрия и графика. – 2024. – Т. 12, № 2. – С. 13-25. – DOIhttps://doi.org/10.12737/2308-4898-2024-12-3-13-25. EDN: https://elibrary.ru/ETWITX
4. Рустамян В.В. αβ-триангуляция на евклидовой плоскости [Текст] / В.В. Рустамян // Геометрия и графика. 2025. Т. 13. № 1. С. 15-25. DOI:https://doi.org/10.12737/2308-4898-2025-13-1-15-25. EDN: https://elibrary.ru/UPGUIU
5. Сальков Н.А. Определение расстояний между геометрическими фигурами интерактивным методом [Текст] / Н.А. Сальков // Геометрия и графика. – 2024. – Т. 12, № 4. – С. 3-14. – DOIhttps://doi.org/10.12737/2308-4898-2024-12-4-3-14. EDN: https://elibrary.ru/SDYIHZ
6. Скворцов А.В., Мирза Н.С. Алгоритмы построения и анализа триангуляции. — Томск: Изд-во Томского университета, 2006. – 168 с. – ISBN 5-7511-2028-0. EDN: https://elibrary.ru/SBVWBL
7. Liu Y., Lee T.-U., Rezaee Javan A., Pietroni N., Xie Y. Reducing the Number of Different Faces in Free-Form Surface Approximations Through Clustering and Optimization. // Computer-Aided Design. 2023. 166. 103633.https://doi.org/10.1016/j.cad.2023.103633.
8. Pellis D., Kilian M., Wang H., Jiang C., Müller C., Pottmann H. Architectural freeform surfaces designed for cost-effective paneling through mold re-use. // Conference: Advances in Architectural Geometry. 2021.
