Geodesic
New modification of the double description method for constructing the skeleton of a polyhedral cone
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 1, pp. 153-163 
N. Yu. Zolotykh. New modification of the double description method for constructing the skeleton of a polyhedral cone. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 1, pp. 153-163. http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a14/
@article{ZVMMF_2012_52_1_a14,
     author = {N. Yu. Zolotykh},
     title = {New modification of the double description method for constructing the skeleton of a polyhedral cone},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {153--163},
     year = {2012},
     volume = {52},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a14/}
}
TY  - JOUR
AU  - N. Yu. Zolotykh
TI  - New modification of the double description method for constructing the skeleton of a polyhedral cone
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2012
SP  - 153
EP  - 163
VL  - 52
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a14/
LA  - ru
ID  - ZVMMF_2012_52_1_a14
ER  - 
%0 Journal Article
%A N. Yu. Zolotykh
%T New modification of the double description method for constructing the skeleton of a polyhedral cone
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2012
%P 153-163
%V 52
%N 1
%U http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_1_a14/
%G ru
%F ZVMMF_2012_52_1_a14

Voir la notice de l'article provenant de la source Math-Net.Ru

A new modification of the double description method is proposed for constructing the skeleton of a polyhedral cone. Theoretical results and a numerical experiment show that the modification is considerably superior to the original algorithm in terms of speed.

[1] Preparata F., Sheimos M., Vychislitelnaya geometriya: Vvedenie, Mir, M., 1989

[2] Avis D., Bremner D., Seidel R., “How good are convex hull algorithms?”, Comput. Geometry: Theory and Arll., 7:5-6 (1997), 265–301 | DOI | MR | Zbl

[3] Motskin T.S., Raifa Kh., Tompson D.L., Troll R.M., “Metod dvoinogo opisaniya”, Matrichnye igry, Fizmatgiz, M., 1961

[4] Burger E., “Über homoge nelineare Ungleichungssysteme”, Angewandte Math. und Mech., 36:3-4 (1956), 135–139 | DOI | MR | Zbl

[5] Chernikova N.V., “Algoritm dlya nakhozhdeniya obschei formuly neotritsatelnykh reshenii sistemy lineinykh uravnenii”, Zh. vychisl. matem. i matem. fiz., 4:4 (1964), 733–738 | MR

[6] Chernikova N.V., “Algoritm dlya nakhozhdeniya obschei formuly neotritsatelnykh reshenii sistemy lineinykh neravenstv”, Zh. vychisl. matem. i matem. fiz., 5:2 (1965), 334–337 | MR

[7] Chernikov S.N., Lineinye neravenstva, Nauka, M., 1968

[8] Veselov S.I., Parubochii I.E., Shevchenko V.N., “Programma nakhozhdeniya ostova konusa neotritsatelnykh reshenii sistemy lineinykh neravenstv”, Sistemnye i prikl. programmy, Ch. 2, Izd-vo Gorkovskogo un-ta, Gorkii, 1984, 83–92

[9] Fernandez F., Quinton P., Extension of Chernikova's algorithm for solving general mixed linear programming problems, Res. Rep. RR0943, INRIA, Rennes, 1988

[10] Le Verge H., A note on Chernikova's algorithm, Res. Rep. RR1662, INRIA, Rennes, 1992

[11] Fukuda K., Prodon A., “Double description method revisited”, Combinatorics and Comput. Sci., 1996, 91–111, Springer, New York | DOI | MR

[12] Shevchenko V.N., Chirkov A.Yu., “O slozhnosti postroeniya ostova konusa”, X Vseros. konf. “Matem. programmirovanie i prilozh.”, UO RAN, Ekaterinburg, 1997, 237

[13] Shevchenko V.N., Gruzdev D.V., “Modifikatsiya algoritma Fure-Motskina dlya postroeniya triangulyatsii”, Diskretnyi analiz i issl. operatsii. Ser. 2, 10:10 (2003), 53–64

[14] Chernykh O.L., “Postroenie vypukloi obolochki konechnogo mnozhestva tochek na osnove triangulyatsii”, Zh. vychisl. matem. i matem. fiz., 31:8 (1991), 1231–1242 | MR

[15] Chaselle B., “An optimal convex hull algorithm in any fixed dimension”, Discrete Comput. Geometry, 1993, no. 10, 377–409 | DOI | MR

[16] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, Mir, M., 1991

[17] Deza M.M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001

[18] Zolotykh N.Yu., Lyalin S.S., “Parallelnyi algoritm nakhozhdeniya obschego resheniya sistemy lineinykh neravenstv”, Vestn. Nizhegorodskogo gos. un-ta, 2009, no. 5, 193–199