Application of the Quickhull algorithm’s principles to the double description method

Authors

  • S.I. Bastrakov
  • N.Yu. Zolotykh

Keywords:

system of linear inequalities
convex hull
polyhedral cone
polyhedron
double description method
Motzkin-Burger algorithm

Abstract

The double description method known also as the Motzkin-Burger algorithm is a method for computing the general solution of a system of linear inequalities. Its new modification applying the ideas of the Quickhull algorithm is proposed. The numerical results demonstrate a number of advantages of the proposed modification over the original double description method and (in many cases) over the Quickhull algorithm. The work was supported by the Russian Foundation for Basic Research (project 09-01-00545-a).

New computational technologies

Downloads

Published

2011-04-25

Issue

Vol. 12 (2011): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biographies

S.I. Bastrakov

Lobachevsky State University of Nizhni Novgorod,
Institute of Information Technology, Mathematics and Mechanics
• Undergraduate

N.Yu. Zolotykh

Lobachevsky State University of Nizhni Novgorod,
Institute of Information Technology, Mathematics and Mechanics
• Associate Professor

References

  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.