The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons

A convex polyhedron is represented as a set of the linear inequalities solutions. Minkowski's sum of two convex polyhedrons $X,Ysubset mathbb{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.

References

1. Schweppe F.C. Recursive State Estimalion: Unknown but Bounded Errors and Systems Inputs. IEEE Tram. Autom. Control, 1968, vol. 13, no. 1, pp. 22-28.
2. Kurzhanskii A.B. Control and observation under uncertainty. Moscow, Nauka, 1977. 392 p. (in Russian)
3. Chernous'ko F.L. Estimation of the Phase State of Dynamical Systems. The Method of Ellipsoids. Moscow, Nauka, 1988. 320 p. (in Russian).
4. Kuntsevich V.M., Lychak M.M. Synthesis of Optimal and Adaptive Control Systems. Kiev, Naukova Dumka, 1985. 245 p.
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, pp. 34-41. (in Russian)
6. Shiryaev V.I. Real Time Minimax Filtration for Multi-step Systems. Control Problems and Information Theory, 1991, no. 5, pp. 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, 2009, vol. 16, no. 4, pp. 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, vol. 2, no. 3, pp. 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, 1965, vol. 5, no. 2, pp. 334-337.
10. Chernikov S.N. Linear Inequalities. Moscow, Nauka, 1968. 488 p. (in Russian)
11. Uhanov M.V. Polygons Sum Construction Algorithm. Bulletin of South Ural State University. Series 'Mathematics, Physics, Chemistry', 2001, vol. 1, no. 7, pp. 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, 2008, vol. 48, no. 7, pp. 1167-1180. (in Russian)
13. Panyukov A.V., Gorbik V.V. Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems. Automation and Remote Control, 2012, vol. 73, no. 2, pp. 276-290.
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), pp. 78-99. (in Russian)
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, 2008, Chelyabinsk, SUSU, pp. 115-122. (in Russian)
16. Bushenkov I.F., Lotov A.V. Independence Linear Inequalities Set Analisys Algorithm. Journal of Computational mathematics and Mathematical Physics, 1980, vol. 20, no. 3, pp. 562-572. (in Russian)
17. Emelichev V.A., Kovalev M.M., Kravtsov M.K. Polyhedrons, Graphs, Optimization. Moscow, Nauka, 1981. (in Russian)