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

Авторы

  • С.И. Бастраков
  • Н.Ю. Золотых

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

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2011-04-25

Выпуск

Том 12 (2011): Выпуск 2.

Раздел

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

Авторы

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

Нижегородский государственный университет им Н.И. Лобачевского,
Институт информационных технологий математики и механики
пр.Гагарина, 23, 603950, Нижний Новгород
• магистрант

Н.Ю. Золотых

Нижегородский государственный университет им Н.И. Лобачевского,
Институт информационных технологий математики и механики
пр.Гагарина, 23, 603950, Нижний Новгород
• доцент

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

  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.