Geodesic
The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 14 (2012), pp. 108-119
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A convex polyhedron is represented as a set of the linear inequalities solutions. Minkowski's sum of two convex polyhedrons $X,Y\subset \mathbb{R}^n$ is polyhedron as well is represented as a set of the linear inequalities solutions. Polynomial algorithm of solving this problem based of forming number of extra inequalities in the summands representation and them translation to resultant representation is presented in the paper. Usage of parallel and distributed computation for effective algorithm Implementation is suggested.
Keywords: polyhedron, Minkowski's sum set, linear inequalities set, linear programming. 
@article{VYURU_2012_14_a10,
     author = {A. V. Panyukov},
     title = {The {Linear} {Inequalities} {Set} {Representation} of {Minkovski's} {Sum} for {Two} {Polyhedrons}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {108--119},
     year = {2012},
     number = {14},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2012_14_a10/}
}
TY  - JOUR
AU  - A. V. Panyukov
TI  - The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2012
SP  - 108
EP  - 119
IS  - 14
UR  - http://geodesic.mathdoc.fr/item/VYURU_2012_14_a10/
LA  - ru
ID  - VYURU_2012_14_a10
ER  - 
%0 Journal Article
%A A. V. Panyukov
%T The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2012
%P 108-119
%N 14
%U http://geodesic.mathdoc.fr/item/VYURU_2012_14_a10/
%G ru
%F VYURU_2012_14_a10
A. V. Panyukov. The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 14 (2012), pp. 108-119. http://geodesic.mathdoc.fr/item/VYURU_2012_14_a10/

[1] F. C. Schweppe, “Recursive state estimalion: unknown but bounded errors and systems inputs”, IEEE Tram. Autom. Control, 13:1 (1968), 22–28 | DOI

[2] Kurzhanskii A. B., Control and observation under uncertainty, Nauka, M., 1977, 392 pp. (in Russian) | MR | Zbl

[3] Chernous'ko F. L., Estimation of the Phase State of Dynamical Systems. The Method of Ellipsoids, Nauka, M., 1988, 320 pp. (in Russian) | MR

[4] Kuntsevich V. M., Lychak M. M., Synthesis of Optimal and Adaptive Control Systems, Naukova Dumka, Kiev, 1985, 245 pp. | MR

[5] Lychak M. M., “Identification and Estimation of State for Control Objects Based on the Plural Method of Attack”, Problems of Control and Informatics, 1999, no. 5, 34–41 (in Russian) | MR

[6] Shiryaev V. I., “Real Time Minimax Filtration for Multi-step Systems”, Control Problems and Information Theory, 1991, no. 5, 805–812 (in Russian)

[7] Shestakov A. L., Sviridjuk G. A., Zaharova E. V., “Dynamic Measurement as a Optimal Control Problem”, Obozrenie prikladnoj i promyshlennoj matematiki, 16:4 (2009), 732 (in Russian)

[8] Uhanov M. V., Shirjaev V. I., “Information Sets Constructiom Algorithms for Minimax Filter Implementation”, Bulletin of South Ural State University. Series «Mathematics, Physics, Chemistry», 2002, no. 3, issue 2, 19–33 (in Russian)

[9] Chernikova N. B., “Algorithm for Finding General Formulas of Non-negative Linear Inequalities Set Solutions”, Journal of Computational mathematics and Mathematical Physics, 5:2 (1965), 334–337 | MR

[10] Chernikov S. N., Linear Inequalities, Nauka, M., 1968, 488 pp. (in Russian) | MR | Zbl

[11] Uhanov M. V., “Polygons Sum Construction Algorithm”, Bulletin of South Ural State University. Series «Mathematics, Physics, Chemistry», 2001, no. 7, issue 1, 39–44 (in Russian)

[12] Lukackij A. M., Shapot D. V., “Constructive Algorithm for Large Scale Set of Inequalities Folging”, Journal of Computational mathematics and Mathematical Physics, 48:7 (2008), 1167–1180 (in Russian) | MR

[13] Panyukov A. V., Gorbik V. V., “Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems”, Automation and Remote Control, 73:2 (2012), 276–290 | MR | Zbl

[14] Panyukov A. V., Tychinin S. A., “Matching Add-Ins Application for Solving MaxTSP”, Bulletin of South Ural State University. Series «Mathematical Modelling, Programming Computer Software», 2008, no. 27 (127), issue 2, 78–99 (in Russian) | Zbl

[15] Panyukov A. V., P'jankov V. A., “Matching Add-Ins Algorithm for Antisymmetrical Traveling Salesman Problem”, Mathematical and Statistical Research of social and Economical Processes, SUSU, Chelyabinsk, 2008, 115–122 (in Russian)

[16] Bushenkov I. F., Lotov A. V., “Independence Linear Inequalities Set Analisys Algorithm”, Journal of Computational mathematics and Mathematical Physics, 20:3 (1980), 562–572 (in Russian) | MR

[17] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Polyhedrons, Graphs, Optimization, Nauka, M., 1981 (in Russian) | MR