Использование идей алгоритма QUICKHULL в методе двойного описания
Ключевые слова:
система линейных неравенств, выпуклая оболочка, конус, полиэдр, метод двойного описания, алгоритм Моцкина-БургераАннотация
Метод двойного описания, известный также как алгоритм Моцкина-Бургера, является одним из методов нахождения общего решения системы линейных неравенств. Предлагается его новая модификация с использованием идей алгоритма Quickhull. Приводятся результаты вычислительного эксперимента, показывающие превосходство предлагаемой модификации над оригинальным методом двойного описания и некоторыми его вариантами, а также ? во многих случаях ? и над алгоритмом Quickhull. Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00545-а).
Библиографические ссылки
Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.
Avis D., Bremner D., Seidel R. How good are convex hull algorithms // Computational Geometry. 1997. 2, N 2. 265-301.
Motzkin T., Raiffa H., Thompson G., Thrall R.M. The double description method // Contributions to the Theory of Games. Princeton: Princeton University Press, 1953. 51-73.
Barber C.B., Dobkin D.P., Huhdanpaa H. The Quickhull algorithm for convex hulls // ACM Transactions on Mathematical Software. 1996. 22, N 4. 469-483.
Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Ж. вычисл. матем. и матем. физ. (направлено).
Черников С.Н. Линейные неравенства. М.: Наука, 1968.
Шевченко В.Н., Груздев Д.В. Модификация алгоритма Фурье-Моцкина для построения триангуляции // Дискр. анализ и исслед. операций. 2003. 10, N 1. 53-64.
Fukuda K., Prodon A. Double description method revisited // Lecture Notes in Computer Science. Vol. 1120.
Черных О.Л. Построение выпуклой оболочки конечного множества точек на основе триангуляции // Ж. вычисл. матем. и матем. физ. 1991. 31, N 8. 1231-1242.
