Вычислительные методы и приложения

Отображение целочисленных множеств и евклидовы приближения

Г. Г. Рябов, В. А. Серов

Научно-исследовательский вычислительный центр Московского государственного университета имени М. В. Ломоносова

Аннотация: Разработка дискретных моделей представления части пространства $R^3$, не обладающей свойством выпуклости, и решения на этих моделях задач маршрутизации с метрикой, приближающейся к евклидовой, продолжает оставаться актуальной в областях робототехники, геоинформатики, компьютерного зрения и проектирования СБИС. В данной работе развивается решеточно-клеточная модель в терминах отображений целочисленных множеств $Z^2$, $Z^3$, $Z^4$ на себя, построения решеточного веера по заданной погрешности модельной метрики, декомпозиции эквидистантного графа и совместного применения решеточных и полиэдральных моделей в программном комплексе метрико-топологических построений.

Ключевые слова: приближение к евклидовой метрике; простые ребра; метрическая окрестность; решеточный веер; веерная триангуляция; эквидистантный граф; топологический процессор.

УДК: 519.6; 514.174.6