Том 10, серия 2, номер 1, 2003 г., Стр. 53-64
УДК 519.852
В. Н. Шевченко, Д. В. Груздев
Модификация алгоритма Фурье–Моцкина для построения триангуляции
Аннотация:
Предлагается итерационный алгоритм построения триангуляции конечного множества точек$A\subset R^d$ , являющейся таким разбиением$d$ -мерной выпуклой оболочки$[A]$ множества$A$ на симплексы с вершинами из$A$ , что пересечением любых двух пересекающихся симплексов является их общая грань. Этот алгоритм является модификацией итерационного алгоритма Фурье–Моцкина [2, 5] построения неприводимой системы неравенств, описывающей$[A]$ . Временная сложность алгоритма не превосходит$O(N^{\lfloor d/2\rfloor+1})$ , где$N=|A|$ , и неулучшаема по порядку при нечетных$d$ .
Библиогр. 10.
Шевченко В. Н. 1
Груздев Д. В. 1
1. Нижегородский государственный университет,
пр. Гагарина, 23, 603950 Нижний Новгород
е-mail: shev@uic.nnov.ru, grclv100@uic.nnov.ru
Статья поступила 27 июня 2002 г.
