# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Tools of mathematical modeling of arbitrary object packing problems. (English) Zbl 1201.90167
Summary: The article reviews the concept of and further develops phi-functions (${\Phi }$-functions) as an efficient tool for mathematical modeling of two-dimensional geometric optimization problems, such as cutting and packing problems and covering problems. The properties of the phi-function technique and its relationship with Minkowski sums and the nofit polygon are discussed. We also describe the advantages of phi-functions over these approaches. A clear definition of the set of objects for which phi-functions may be derived is given and some exceptions are illustrated. A step by step procedure for deriving phi-functions illustrated with examples is provided including the case of continuous rotation.
##### MSC:
 90C27 Combinatorial optimization
##### References:
 [1] Bennell, J. A., & Song, X. (2008). A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums. Computers and Operational Research, 35(1), 267–281. · Zbl 1136.65023 · doi:10.1016/j.cor.2006.02.026 [2] Burke, E. K., Hellier, R. S. R., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179(1), 27–49. · Zbl 1175.90325 · doi:10.1016/j.ejor.2006.03.011 [3] Culberson, J. C., & Reckhow, R. A. (1988). Covering polygons is hard. In Proceedings of 29th IEEE conference on foundations of computer science (pp. 601–611). [4] Cunninghame-Green, R. (1989). Geometry. Shoemaking and the milk tray problem. New Scientist, 1677, 50–53. [5] Daniels, K., & Inkulu, R. (2001). Translational polygon covering using intersection graphs. In Proceedings of the thirteenth Canadian conference on computational geometry (pp. 61–64). [6] Daniels, K., Mathur, A., & Grinde, R. (2003). A combinatorial maximum cover approach to 2D translational geometric covering. In Proceeedings of 15th Canadian conference on computational geometry (pp. 2–5). Halifax, Nova Scotia, Canada, August 11–13, 2003. [7] Fomenko, A., Fuchs, D., & Gutenmacher, V. (1986). Homotopic topology. Akademiai Kiado: Budapest. [8] Ghosh, P. K. (1991). An algebra of polygons through the notation of negative shapes. CVGIP: Imag Understand, 17, 357–378. [9] Scheithauer, G., Stoyan, Y., Gil, N., & Romanova, T. (2003). Phi-functions for circular segments. Prepr. Technische Univarsitat Dresden, MATH-NM-7-2003. Dresden. [10] Stoyan, Y. (1983). Mathematical methods for geometric design. In Advances in CAD/CAM//. Proceeding PROLAMAT82. Leningrad, USSR, 16–18 May, 1982 (pp. 67–86). Amsterdam: North-Holland. [11] Stoyan, Y. (2003). Phi-function of non-convex polygons with rotations. Journal of Mechanical Engineering, 6(1), 74–86. [12] Stoyan, Y., & Gil, N. (1976). Methods and algorithms of placement of 2D geometric objects. Ukrainian SSR academy of sciences. Kiev: Naukova Dumka (In Russian). [13] Stoyan, Y., & Pankratov, A. V. (1999). Regular packing of congruent polygons on the rectangular sheet. European Journal of Operational Research, 113, 653–675. · Zbl 0941.90065 · doi:10.1016/S0377-2217(98)00050-2 [14] Stoyan, Y., & Patsuk, V. N. (2000). A method of optimal lattice packing of congruent oriented polygons in the plane. European Journal of Operational Research, 124, 204–216. · Zbl 0990.90103 · doi:10.1016/S0377-2217(99)00115-0 [15] Stoyan, Y., & Ponomarenko, L. D. (1977). Minkowski’s sum and the hodograph of the dense allocation vector function. Reports of the Ukrainian SSR Academy of Science, A(10), 888–890 (In Russian). [16] Stoyan, Y., Novozhilova, M., & Kartashov, A. (1996). Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. European Journal of Operational Research, 92, 193–210. · Zbl 0916.90234 · doi:10.1016/0377-2217(95)00038-0 [17] Stoyan, Y., Terno, J., Scheithauer, G., Gil, N., & Romanova, T. (2002a). Phi-functions for primary 2D-objects. Studia Informatica Universalis, 2(1), 1–32. [18] Stoyan, Y., Terno, J., Gil, M., Romanova, T., & Scheithauer, G. (2002b). Construction of a Phi-function for two convex polytopes. Applicationes Mathematicae, 29(2), 199–218. · Zbl 1053.90009 · doi:10.4064/am29-2-6 [19] Stoyan, Y., Scheithauer, G., Gil, N., & Romanova, T. (2004). Phi-functions for complex 2D-objects. 4OR (Operations Research): Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2, 69–84. [20] Stoyan, Y., Scheithauer, G., & Romanova, T. (2005a). Mathematical modeling of interaction of primary geometric 3D objects. Cybernetics and Systems Analysis, 41(3), 332–342. Translated from Kibernetika i Sistemnyi Analiz, 3, 19–31. · Zbl 1102.68684 · doi:10.1007/s10559-005-0067-y [21] Stoyan, Y., Gil, N., Scheithauer, G., Pankratov, A., & Magdalina, I. (2005b). Packing of convex polytopes into a parallelepiped. Optimization, 54(2), 215–235. · Zbl 1134.90550 · doi:10.1080/02331930500050681 [22] Toth, G. F. (1997). Packing and covering. In J. Goodman & J. O’Rourke (Eds.), Handbook of discrete and computational geometry. New York: CRC Press.