Новый алгоритм для вычисления индексов пересечения циклов

Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2022. № 3. С. 3–10.

Яковлев Е. И.

Актуальность и цели. Объекты исследования – триангулированные компактные полиэдры P, являющиеся n -мерными многообразиями с краем. Цель – создание новых эффективных алгоритмов для вычисления индексов пересечения по модулю 2. Материалы и методы. Используется построение замкнутого n--мерного пути вдоль заданного абсолютного одномерного цикла x . Результаты. Разработан
алгоритм, позволяющий вычислить индекс пересечения заданного абсолютного одномерного цикла x с произвольным относительным циклом размерности (n −1) . Дано строгое математическое обоснование алгоритма. Выводы. Для рассматриваемой задачи алгоритм решения разработан впервые. Его вычислительная сложность равна O(n2N + m), где n – размерность многообразия P; N – количество его n -мерных симплексов; m – количество ребер, из которых состоит цикл x .

Ключевые слова: алгоритм, цикл, полиэдр, algorithm, Polyhedron, индекс пересечения, cycle, intersection index

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Теория динамических систем и ее приложения (2023)