Математика
Новый алгоритм для вычисления индексов пересечения циклов
Е. И. Яковлев Национальный исследовательский университет «Высшая школа экономики», Нижний Новгород
Аннотация:
Актуальность и цели. Объекты исследования - триангулированные компактные полиэдры
$P$, являющиеся
$n$-мерными многообразиями с краем. Цель - создание новых эффективных алгоритмов для вычисления индексов пересечения по модулю
$2$.
Материалы и методы. Используется построение замкнутого
$n$-мерного пути вдоль заданного абсолютного одномерного цикла
$x$.
Результаты. Разработан алгоритм, позволяющий вычислить индекс пересечения заданного абсолютного одномерного цикла
$x$ с произвольным относительным циклом размерности
$(n - 1)$. Дано строгое математическое обоснование алгоритма.
Выводы. Для рассматриваемой задачи алгоритм решения разработан впервые. Его вычислительная сложность равна
$O(n^{2}N+m)$, где
$n$ - размерность многообразия
$P$;
$N$ - количество его
$n$-мерных симплексов;
$m$ - количество ребер, из которых состоит цикл
$x$.
Ключевые слова:
алгоритм, полиэдр, цикл, индекс пересечения.
УДК:
519.712.6
DOI:
10.21685/2072-3040-2022-3-1