Использование идей алгоритма QUICKHULL в методе двойного описания

Авторы

Ключевые слова:

система линейных неравенств, выпуклая оболочка, конус, полиэдр, метод двойного описания, алгоритм Моцкина-Бургера

Аннотация

Метод двойного описания, известный также как алгоритм Моцкина-Бургера, является одним из методов нахождения общего решения системы линейных неравенств. Предлагается его новая модификация с использованием идей алгоритма Quickhull. Приводятся результаты вычислительного эксперимента, показывающие превосходство предлагаемой модификации над оригинальным методом двойного описания и некоторыми его вариантами, а также ? во многих случаях ? и над алгоритмом Quickhull. Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00545-а).

Авторы

С.И. Бастраков

Н.Ю. Золотых

Библиографические ссылки

  1. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.
  2. Avis D., Bremner D., Seidel R. How good are convex hull algorithms // Computational Geometry. 1997. 2, N 2. 265-301.
  3. 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.
  4. 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.
  5. Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Ж. вычисл. матем. и матем. физ. (направлено).
  6. Черников С.Н. Линейные неравенства. М.: Наука, 1968.
  7. Шевченко В.Н., Груздев Д.В. Модификация алгоритма Фурье-Моцкина для построения триангуляции // Дискр. анализ и исслед. операций. 2003. 10, N 1. 53-64.
  8. Fukuda K., Prodon A. Double description method revisited // Lecture Notes in Computer Science. Vol. 1120.
  9. Черных О.Л. Построение выпуклой оболочки конечного множества точек на основе триангуляции // Ж. вычисл. матем. и матем. физ. 1991. 31, N 8. 1231-1242.

Загрузки

Опубликован

25-04-2011

Как цитировать

Бастраков С., Золотых Н. Использование идей алгоритма QUICKHULL в методе двойного описания // Вычислительные методы и программирование. 2011. 12. 232-237

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Наиболее читаемые статьи этого автора (авторов)