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

Authors

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).

Author Biographies

S.I. Bastrakov

N.Yu. Zolotykh

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.

Published

25-04-2011

How to Cite

Бастраков С., Золотых Н. Application of the Quickhull algorithm’s Principles to the Double Description Method // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2011. 12. 232-237

Issue

Section

Section 1. Numerical methods and applications

Most read articles by the same author(s)