Configuration space of geometric objects. (English. Russian original) Zbl 1420.55028
Cybern. Syst. Anal. 54, No. 5, 716-726 (2018); translation from Kibern. Sist. Anal. 2018, No. 5, 38-50 (2018).
This paper reviews the concept of configuration space of geometric objects as it is applied to various placement, packing and covering problems. Extensive references to the literature are included. At the end of the paper the authors define generalized \(\Phi\)-functions and normalized generalized \(\Phi\)-functions.
Reviewer: Rabe von Randow (Bonn)
MSC:
| 55R80 | Discriminantal varieties and configuration spaces in algebraic topology |
| 05B40 | Combinatorial aspects of packing and covering |
| 52C17 | Packing and covering in \(n\) dimensions (aspects of discrete geometry) |
Keywords:
geometric object; configuration space; generalized variables; layout; packing problems; covering problemsReferences:
| [1] | B. Grunbaum, “Configurations of points and lines” in: Graduate Studies in Mathematics, American Mathematical Society, Vol. 103, Providence, Rhode Island (2009). · Zbl 1205.51003 |
| [2] | Pisanski, Tomaž; Servatius, Brigitte, Combinatorial Configurations, 157-196 (2012), Boston · Zbl 1277.05001 |
| [3] | C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, CRC Press (2010). · Zbl 0836.00010 |
| [4] | H. Gropp, “Configurations between geometry and combinatorics,” Discrete Applied Mathematics, Vol. 138, No. 1, 79-88 (2004). · Zbl 1045.51002 · doi:10.1016/S0166-218X(03)00271-3 |
| [5] | C. Berge, Principes de combinatoire, Dunod, Paris (1968). · Zbl 0227.05001 |
| [6] | H. J. Ryser, “Combinatorial configurations,” SIAM J. on Applied Mathematics, Vol. 17, No. 3, 593-602 (1969). · Zbl 0186.01901 · doi:10.1137/0117056 |
| [7] | V. I. Arnold, Mathematical Methods of Classical Mechanics [in Russian], Nauka, Moscow (1989). · Zbl 0692.70003 · doi:10.1007/978-1-4757-2063-1 |
| [8] | Solla, SA; Sorkin, GB; White, SR; Bienenstock, E. (ed.); etal., Configuration space analysis for optimization problems, 283-293 (1986), Berlin-Heidelberg · Zbl 1356.90126 · doi:10.1007/978-3-642-82657-3_28 |
| [9] | E. Fadell and L. Neuwirth, “Configuration space,” Math. Scand., Vol. 10, 111-118 (1962). · Zbl 0136.44104 · doi:10.7146/math.scand.a-10517 |
| [10] | C. Westerland, “Configuration spaces in geometry and topology,” Australian Mathematical Society Gazette, Vol. 38, No. 5, 279-283 (2011). · Zbl 1257.55013 |
| [11] | E. R. Fadell and S. Y. Husseini, Geometry and Topology of Configuration Spaces, Springer Monographs in Mathematics (2001). · Zbl 0962.55001 |
| [12] | F. R. Cohen and S. Gitler, “On loop spaces of configuration spaces,” Trans. Amer. Math. Soc., Vol. 354, No. 5, 1705-1748 (2002). · Zbl 0992.55006 · doi:10.1090/S0002-9947-02-02948-3 |
| [13] | Y. G. Stoyan, “Mathematical methods for geometric design,” in: Advances in CAD/CAM, Proc. of PROLAMAT82, May 1982, Leningrad, USSR, North-Holland, Amsterdam (2003). |
| [14] | Yu. G. Stoyan and S. V. Yakovlev, Mathematical Models and Optimization Methods in Geometric Design [in Russian], Naukova Dumka, Kyiv (1986). |
| [15] | Y. Stoyan, M. Gil, J. Terno, T. Romanova, and G. Schithauer, “Φ-function for complex 2D objects,” 4OR — Quarterly J. of the Belgian, French and Italian Operations Research Societies, Vol. 2, No. 1, 69-84 (2004). · Zbl 1125.90382 |
| [16] | Yu. Stoyan, G. Scheithauer, and T. Romanova, “Mathematical modeling of interaction of primary geometric 3D objects,” Cybern. Syst. Analysis, Vol. 41, No. 3, 332-342 (2005). · Zbl 1102.68684 · doi:10.1007/s10559-005-0067-y |
| [17] | Stoyan, Y.; Romanova, T.; Fasano, G. (ed.); Pintér, J. (ed.), Mathematical models of placement optimization: Two- and three-dimensional problems and applications, No. 73, 363-388 (2013), New York · Zbl 1365.90163 · doi:10.1007/978-1-4614-4469-5_15 |
| [18] | J. Bennell, G. Scheithauer, Y. G. Stoyan, and T. Romanova, “Tools of mathematical modelling of arbitrary object packing problems,” J. Annals of Operations Research, Springer Netherlands Publ., Vol. 179, No. 1, 343-368 (2010). · Zbl 1201.90167 · doi:10.1007/s10479-008-0456-5 |
| [19] | N. Chernov, Y. Stoyan, and T. Romanova, “Mathematical model and efficient algorithms for object packing problem,” Computational Geometry: Theory and Applications, Vol. 43, No. 5, 535-553 (2010). · Zbl 1228.05117 · doi:10.1016/j.comgeo.2009.12.003 |
| [20] | Stoyan, Y.; Romanova, T.; Pankratov, A.; Chugay, A.; Fasano, G. (ed.); Pintér, JD (ed.), Optimized object packings using quasi-phi-functions, No. 105, 265-293 (2015), New York · Zbl 1390.90483 · doi:10.1007/978-3-319-18899-7_13 |
| [21] | Stoyan, Y.; Pankratov, A.; Romanova, T.; Butenko, S. (ed.); etal., Placement problems for irregular objects: Mathematical modeling, optimization and applications, 521-558 (2017), New York · Zbl 1398.90225 · doi:10.1007/978-3-319-68640-0_25 |
| [22] | V. L. Rvachev, R-Functions Theory and Some of its Applications [in Russian], Naukova Dumka, Kyiv (1982). · Zbl 0521.65084 |
| [23] | Hulianytskyi, L.; Riasna, I.; Butenko, S. (ed.); etal., Formalization and classification of combinatorial optimization problems, 239-250 (2017), New York · Zbl 1398.90140 · doi:10.1007/978-3-319-68640-0_11 |
| [24] | I. V. Sergienko, L. F. Hulianytskyi, and S. I. Sirenko, “Classification of applied methods of combinatorial optimization,” Cybern. Syst. Analysis, Vol. 45, No. 5, 732-744 (2009). · Zbl 1188.90220 · doi:10.1007/s10559-009-9134-0 |
| [25] | A. Bortfeldt and G. Wascher, “Constraints in container loading: A state of the art review,” Europ. J. of Operational Research, Vol. 229, No. 1, 1-20 (2013). · Zbl 1317.90172 · doi:10.1016/j.ejor.2012.12.006 |
| [26] | Fasano, G.; Fasano, G. (ed.); Pintér, JD (ed.), A modeling-based approach for non-standard packing problems, No. 105, 67-85 (2015), New York · Zbl 1384.90084 · doi:10.1007/978-3-319-18899-7_4 |
| [27] | M. Hifi and R. M’Hallah, “A literature review on circle and sphere packing problems: Model and methodologies,” Advances in Optimization Research, Vol. 2009, 1-22 (2009). · Zbl 1198.90337 · doi:10.1155/2009/150624 |
| [28] | E. G. Birgin, J. M. Martinez, F. H. Nishihara, and D. P. Ronconi, “Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization,” Comput. Oper. Res., Vol. 33, 3535-3548 (2006). · Zbl 1110.90072 · doi:10.1016/j.cor.2005.03.031 |
| [29] | J. Egeblad, B. K. Nielsen, and M. Brazil, “Translational packing of arbitrary polyhedral,” Comp. Geom., Vol. 142, No. 4, 269-288 (2009). · Zbl 1178.90286 · doi:10.1016/j.comgeo.2008.06.003 |
| [30] | G. A. Fasano, “Global optimization point of view for non-standard packing problems,” J. of Global Optimization, Vol. 155, No. 2, 279-299 (2013). · Zbl 1268.90062 · doi:10.1007/s10898-012-9865-8 |
| [31] | Yu. Stoyan, A. Pankratov, and T. Romanova, “Cutting and packing problems for irregular objects with continuous rotations: Mathematical modeling and nonlinear optimization,” J. of Operational Research Society, Vol. 167, No. 5, 786-800 (2016). · doi:10.1057/jors.2015.94 |
| [32] | A. Drira, H. Pierreval, and S. Hajri-Gabouj, “Facility layout problems: A survey,” Annual Reviews in Control, Vol. 31, No. 2, 255-267 (2007). · doi:10.1016/j.arcontrol.2007.04.001 |
| [33] | Fadel, GM; Wiecek, MM; Fasano, G. (ed.); Pintér, J. (ed.), Packing optimization of free-form objects in engineering design, No. 105, 37-66 (2015), New York · Zbl 1390.90581 · doi:10.1007/978-3-319-18899-7_3 |
| [34] | Yu. G. Stoyan, V. V. Semkin, and A. M. Chugay, “Optimization of 3D objects layout into a multiply connected domain with account for shortest distances,” Cybern. Syst. Analysis, Vol. 50, No. 3, 374-385 (2014). · Zbl 1311.93007 · doi:10.1007/s10559-014-9626-4 |
| [35] | Zhi-Guo Sun and Hong-Fei Teng, “Optimal layout design of a satellite module,” Engineering Optimization, Vol. 35, No. 5, 513-529 (2003). · doi:10.1080/03052150310001602335 |
| [36] | Stoyan, Y.; Romanova, T.; Pankratov, A.; Kovalenko, A.; Stetsyuk, P.; Fasano, G. (ed.); Pintér, J. (ed.), Balance layout problems: Mathematical modeling and nonlinear optimization, No. 114, 369-400 (2016), New York · Zbl 1380.90170 |
| [37] | Yi-Chun Xu, Ren-Bin Xiao, and M. Amos, “A novel genetic algorithm for the layout optimization problem,” in: 2007 IEEE Congr. on Evolutionary Computation, CEC 2007 (2007), pp. 3938-3942. |
| [38] | Yu. G. Stoyan, V. Z. Sokolovskii, and S. V. Yakovlev, “Method of balancing rotating discretely distributed masses,” Energomashinostroenie, No. 2, 4-5 (1982). |
| [39] | Y. G. Stoyan, S. V. Yakovlev, and O. V. Parshin, “Quadratic optimization on combinatorial sets in <Emphasis Type=”Italic“>R <Emphasis Type=”Italic“>n ,” Cybern. Syst. Analysis, Vol. 27, No. 4, 561-567 (1991). · doi:10.1007/BF01130367 |
| [40] | A. Bortfeldt and G. Wascher, “Constraints in container loading: A state of the art review,” Europ. J. of Operational Research, Vol. 229, No. 1, 1-20 (2013). · Zbl 1317.90172 · doi:10.1016/j.ejor.2012.12.006 |
| [41] | Yu. G. Stoyan and V. M. Patsuk, “Covering a convex 3D polytope by a minimal number of congruent spheres,” Intern. J. of Computer Mathematics, Vol. 91, No. 9, 2010-2020 (2014). · Zbl 1308.52009 · doi:10.1080/00207160.2013.865726 |
| [42] | S. V. Yakovlev, “On a class of problems on covering of a bounded set,” Acta Mathematica Hungarica, Vol. 53, No. 3, 253-262 (1989). · Zbl 0684.52007 · doi:10.1007/BF01953365 |
| [43] | S. N. Gerasin, V. V. Shlyakhov, and S. V. Yakovlev, “Set coverings and tolerance relations,” Cybern. Syst. Analysis, Vol. 44, No. 3, 333-340 (2008). · Zbl 1158.08002 · doi:10.1007/s10559-008-9007-y |
| [44] | S. B. Shekhovtsov and S. V. Yakovlev, “Formalization and solution of one class of covering problem in design of control and monitoring systems,” Autom. Remote Control, Vol. 50, No. 5, 705-710 (1989). · Zbl 0705.90073 |
| [45] | E. M. Kiseleva, L. I. Lozovskaya, and E. V. Timoshenko, “Solution of continuous problems of optimal covering with spheres using optimal set-partition theory,” Cybern. Syst. Analysis, Vol. 45, No. 3, 421-437 (2009). · Zbl 1182.49045 · doi:10.1007/s10559-009-9113-5 |
| [46] | E. M. Kiseleva and L. S. Koriashkina, Models and Methods of the Solution of Continuous Problems of Optimal Partition of Sets: Linear, Nonlinear, and Dynamic Problems [in Russian], Naukova Dumka, Kyiv (2013). |
| [47] | E. M. Kiseleva and L. S. Koriashkina, “Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations,” Cybern. Syst. Analysis, Vol. 51, No. 3, 325-335 (2015). · Zbl 1327.90261 · doi:10.1007/s10559-015-9725-x |
| [48] | Yu. G. Stoyan, S. V. Yakovlev, and O. S. Pichugina, Euclidean Combinatorial Configurations [in Russian], Konstanta, Kharkiv (2017). |
| [49] | Yakovlev, S.; Butenko, S. (ed.); etal., Convex extensions in combinatorial optimization and their applications, 567-584 (2017), New York · Zbl 1398.90145 · doi:10.1007/978-3-319-68640-0_27 |
| [50] | O. S. Pichugina and S. V. Yakovlev, “Continuous representations and functional extensions in combinatorial optimization,” Cybern. Syst. Analysis, Vol. 52, No. 6, 921-930 (2016). · Zbl 1355.90089 · doi:10.1007/s10559-016-9894-2 |
| [51] | S. V. Yakovlev, “Bounds on the minimum of convex functions on Euclidean combinatorial sets,” Cybernetics, Vol. 25, No. 3, 385-391 (1989). · Zbl 0748.90057 · doi:10.1007/BF01069996 |
| [52] | S. V. Yakovlev and I. V. Grebennik, “Localization of solutions of some problems of nonlinear integer optimization,” Cybern. Syst. Analysis, Vol. 29, No. 5, 727-734 (1993). · Zbl 0820.90078 · doi:10.1007/BF01125802 |
| [53] | S. V. Yakovlev and O. A. Valuiskaya, “Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints,” Ukrainian Mathematical J., Vol. 53(9), 1535-1545 (2001). · Zbl 0994.90140 · doi:10.1023/A:1014374926840 |
| [54] | S. V. Yakovlev and O. S. Pichugina, “Properties of combinatorial optimization problems over polyhedral-spherical sets,” Cybern. Syst. Analysis, Vol. 54, No. 1, 99-109 (2018). · Zbl 1390.90489 · doi:10.1007/s10559-018-0011-6 |
| [55] | O. Pichugina and S. Yakovlev, “Optimization on polyhedral-spherical sets: Theory and applications,” in: Proc. 2017 IEEE First Ukrain. Conf. on Electrical and Computer Engeneering, UKRCON (2017), pp. 1167-1175. |
| [56] | S. V. Yakovlev, “The method of artificial dilation in problems of optimal packing of geometric objects,” Cybern. Syst. Analysis, Vol. 53, No. 5, 725-731 (2017). · Zbl 1392.90099 · doi:10.1007/s10559-017-9974-y |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
