# 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)
Rotational polygon overlap minimization and compaction. (English) Zbl 0904.68174
Summary: An effective and fast algorithm is given for rotational overlap minimization: given an overlapping layout of polygons $P_1, P_2, P_3, \dots, P_k$ in a container polygon $Q$, translate and rotate the polygons to diminish their overlap to a local minimum. A (local) overlap minimum has the property that any perturbation of the polygons increases the overlap. Overlap minimization is modified to create a practical algorithm for compaction: starting with a non-overlapping layout in a rectangular container, plan a non-overlapping motion that diminishes the length or area of the container to a local minimum. Experiments show that both overlap minimization and compaction work well in practice and are likely to be useful in industrial applications.

##### MSC:
 68U05 Computer graphics; computational geometry
##### Keywords:
rotational overlap minimization
Full Text:
##### References:
 [1] El-Aal, R. M. S. Abd: A new technique for nesting irregular shapes based on rectangular modules. Current adv. Mech. design production 6, 533-540 (1996) [2] Agarwal, P.; Amenta, N.; Sharir, M.: Largest placement of one convex polygon inside another. Proceedings of the second workshop on algorithmic foundations of robotics (July 1996) · Zbl 0892.68101 [3] Avnaim, F.; Boissonnat, J.: Polygon placement under translation and rotation. Lecture notes in computer science 294, 322-333 (1988) · Zbl 0644.68073 [4] Bounsaythip, C.; Maouche, S.: Irregular shape nesting and placing with evolutionary approach. Computational cybernetics and simulation (Cat. No. 97CH36088-5), 5 (12--15 October 1997) [5] Chang, J. S.; Yap, C. K.: A polynomial solution for the potato-peeling problem. Discrete comput. Geom. 1, 155-182 (1986) · Zbl 0593.52007 [6] Chazelle, B.: The polygon containment problem. Advances in computing research, vol. 1: computational geometry 1, 1-33 (1983) [7] Daniels, K.: Containment algorithms for nonconvex polygons with applications to layout. Ph.d. thesis (1995) [8] Dobkin, D.; Hershberger, J.; Kirkpatrick, D.; Suri, S.: Computing the intersection-depth of polyherdra. Algorithmica 9, 518-533 (1993) · Zbl 0797.68162 [9] Dowsland, K. A.; Dowsland, W. B.: Solution approaches to irregular nesting problems. European J. Oper. res. 84, No. 3, 506-521 (1995) · Zbl 0918.90116 [10] Grinde, R. B.; Cavalier, T. M.: A new algorithm for the two-polygon containment problem. Comput. oper. Res. (1996) · Zbl 0912.90238 [11] Guibas, L.; Ramshaw, L.; Stolfi, J.: A kinetic framework for computational geometry. Proceedings of the 24th IEEE symposium on foundations of computer science, 100-111 (1983) [12] Han, G. C.; Na, S. J.: Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing. J. engrg. Manufacture 210, No. B6, 509-519 (1996) [13] Heckmann, R.; Lengauer, T.: Computing upper and lower bounds on textile nesting problems. Lecture notes in computer science 1136, 392-405 (1996) [14] Jain, P.; Fenyes, P.; Richter, R.: Optimal blank nesting using simulated annealing. J. mech. Design 114, No. 1, 160-165 (1992) [15] Lamousin, H. J.; Waggenspack, W. N.; Dobson, G. T.: Nesting of complex 2-D parts within irregular boundaries. J. mech. Design 118, No. 4, 615 (1996) [16] Li, Z.: Compaction algorithms for nonconvex polygons and their applications. Ph.d. thesis (1994) [17] Li, Z.; Milenkovic, V.: The complexity of compaction problem. Proc. 5th canad. Conf. comput. Geom., 7-11 (1993) [18] Li, Z.; Milenkovic, V.: Compaction and separation algorithms for nonconvex polygons and their applications. European J. Oper. res. 84, 539-561 (1995) · Zbl 1127.90403 [19] Milenkovic, V.: Translation polygon containment and minimal enclosure using linear programming based restriction. Proc. 28th annu. ACM sympos. Theory comput. (STOC 96), 109-118 (1996) · Zbl 0922.68129 [20] Milenkovic, V.: Position-based physics: simulating the motion of many highly interacting spheres and polyhedra. Computer graphics, proc. SIGGRAPH ’96, 129-136 (1996) [21] Milenkovic, V. J.: Multiple translation containment, part II: Exact algorithms. Algorithmica 19, 183-218 (1997) · Zbl 0882.68142 [22] Milenkovic, V.; Daniels, K.: Translation polygon containment and minimal enclosure using geometric algorithms and mathematical programming. Technical report 25-95 (1995) [23] Milenkovic, V.; Daniels, K. M.: Translational polygon containment and minimal enclosure using mathematical programming. Internat. trans. Oper. res. (1997) · Zbl 0883.68127 [24] Prasad, Y. K. D.V.; Somasundaram, S.; Rao, K. P.: A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks. Internat. J. Production res. 33, No. 6, 1505-1520 (1995) · Zbl 0917.90241 [25] Stoyan, Yu.G.; Novozhilova, M. V.; Kartashov, A. V.: Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. European J. Oper. res. 92, 193-210 (1996) · Zbl 0916.90234