×

Scandinavian thins on top of cake: new and improved algorithms for stacking and packing. (English) Zbl 1303.68143

Summary: We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] See http://en.wikipedia.org/wiki/Ginger_biscuit
[2] See http://www.annasthins.ca/ · Zbl 0582.68067
[3] See http://en.wikipedia.org/wiki/Cat_flap
[4] See http://pack-any-shape.com/ · Zbl 1019.68117
[5] Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606-635 (2004) · Zbl 1204.68240
[6] Agarwal, P. K.; Sharir, M.; Sack, J.-R. (ed.); Urrutia, J. (ed.), Davenport-Schinzel sequences and their geometric applications, 1-47 (2000), Amsterdam · Zbl 0952.68148
[7] Ahn, H.-K.; Bae, S. W.; Cheong, O.; Gudmundsson, J.; Tokuyama, T.; Vigneron, A.; Fernández-Baca, D. (ed.), A generalization of the convex Kakeya problem, Arequipa, Peru, April 16-20, 2012, Berlin · Zbl 1297.52003
[8] Ahn, H.-K., Brass, P., Shin, C.-S.: Maximum overlap and minimum convex hull of two convex polyhedra under translations. Comput. Geom., Theory Appl. 40(2), 171-177 (2008) · Zbl 1137.52004
[9] Ahn, H.-K., Cheng, S.-W., Reinbacher, I.: Maximum overlap of convex polytopes under translation. Comput. Geom., Theory Appl. 46(5), 552-565 (2013) · Zbl 1264.52009
[10] Ahn, H.-K.; Cheong, O., Stacking and bundling two convex polygons, Sanya, Hainan, China, December 19-21 · Zbl 1175.68485
[11] Ahn, H.-K., Cheong, O.: Aligning two convex figures to minimize area or perimeter. Algorithmica 62(1-2), 464-479 (2012) · Zbl 1311.68161
[12] Ahn, H.-K., Cheong, O., Park, C.-D., Shin, C.-S., Vigneron, A.: Maximizing the overlap of two planar convex sets under rigid motions. Comput. Geom., Theory Appl. 37(1), 3-15 (2007) · Zbl 1115.65016
[13] Alt, H.; Blömer, J.; Wagener, H.; Paterson, M. (ed.), Approximation of convex polygons, Warwick University, England, July 16-20, 1990, Berlin · Zbl 0765.68201
[14] Alt, H., Fuchs, U., Rote, G., Weber, G.: Matching convex shapes with respect to the symmetric difference. Algorithmica 21(1), 89-103 (1998) · Zbl 0896.68150
[15] Alt, H.; Hurtado, F.; Akiyama, J. (ed.); Kano, M. (ed.); Urabe, M. (ed.), Packing convex polygons into rectangular boxes, Japanese Conference, JCDCG 2000, Tokyo, Japan, November, 22-25, Berlin · Zbl 0998.68189
[16] Aonuma, H.; Imai, H.; Imai, K.; Tokuyama, T., Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams, 225-234 (1990), New York
[17] Arkin, E. M.; Efrat, A.; Hart, G.; Kostitsyna, I.; Kröller, A.; Mitchell, J. S.B.; Polishchuk, V.; Kranakis, E. (ed.); Krizanc, D. (ed.); Luccio, F. L. (ed.), Scandinavian thins on top of cake: on the smallest one-size-fits-all box, FUN 2012, Venice, Italy, June 4-6, 2012, Berlin
[18] Arkin, E.M., Khuller, S., Mitchell, J.S.B.: Geometric knapsack problems. Algorithmica 10, 399-427 (1993) · Zbl 0781.68109
[19] Avnaim, F.; Boissonnat, J.-D., Simultaneous containment of several polygons, 242-250 (1987)
[20] Baker, B.S., Fortune, S.J., Mahaney, S.R.: Polygon containment under translation. J. Algorithms 7, 532-548 (1986) · Zbl 0621.51021
[21] Barequet, G., Har-Peled, S.: Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geom. Appl. 11, 465-474 (2001) · Zbl 1074.68629
[22] Becker, B., Franciosa, P.G., Gschwind, S., Leonardi, S., Ohler, T., Widmayer, P.: Enclosing a set of objects by two minimum area rectangles. J. Algorithms 21(3), 520-541 (1996) · Zbl 0864.68104
[23] Bhattacharya, B. K.; Mukhopadhyay, A.; Akiyama, J. (ed.); Kano, M. (ed.), On the minimum perimeter triangle enclosing a convex polygon, No. 2866, 84-96 (2003), Berlin · Zbl 1179.52012
[24] Bose, P., Mora, M., Seara, C., Sethia, S.: On computing enclosing isosceles triangles and related problems. Int. J. Comput. Geom. Appl. 21(1), 25-45 (2011) · Zbl 1221.65058
[25] Boyce, J.E., Dobkin, D.P., Drysdale, R.L. III, Guibas, L.J.: Finding extremal polygons. SIAM J. Comput. 14, 134-147 (1985) · Zbl 0557.68034
[26] Brass, P.; Cheong, O.; Na, H. S.; Shin, C. S.; Vigneron, A., Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon, No. 3106, 259-267 (2004), Berlin · Zbl 1091.68109
[27] Cabello, S., de Berg, M., Giannopoulos, P., Knauer, C., van Oostrum, R., Veltkamp, R.C.: Maximizing the area of overlap of two unions of disks under rigid motion. Int. J. Comput. Geom. Appl. 19(6), 533-556 (2009) · Zbl 1194.65035
[28] Chan, T.M.: Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom., Theory Appl. 35(1-2), 20-35 (2006) · Zbl 1103.65064
[29] Chang, J.S.: Polygon optimization problems. Report 240. CS, NYU, New York (1986) · Zbl 1218.52015
[30] Chang, J.S., Yap, C.K.: A polynomial solution for the potato-peeling problem. Discrete Comput. Geom. 1, 155-182 (1986) · Zbl 0593.52007
[31] Chazelle, B.M.: The polygon containment problem. Adv. Comput. Res. 1, 1-33 (1983)
[32] Daniels, K., Milenkovic, V.J.: Multiple translational containment, Part I: An approximate algorithm. Algorithmica 19(1-2), 148-182 (1997) · Zbl 0883.68127
[33] de Berg, M., Cheong, O., Devillers, O., van Kreveld, M.J., Teillaud, M.: Computing the maximum overlap of two convex polygons under translations. Theory Comput. Syst. 31(5), 613-628 (1998) · Zbl 0910.68226
[34] de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008) · Zbl 1140.68069
[35] DePano, N.A.A.: Polygon approximation with optimized polygonal enclosures: applications and algorithms. Ph.D. thesis, Department of Computer Science, Johns Hopkins University (1987)
[36] DePano, N. A.A.; Aggarwal, A., Finding restricted k-envelopes for convex polygons, 81-90 (1984)
[37] Egeblad, J., Nielsen, B.K., Brazil, M.: Translational packing of arbitrary polytopes. Comput. Geom., Theory Appl. 42(4), 269-288 (2009) · Zbl 1178.90286
[38] Freeman, H., Shapira, R.: Determining the minimum-area encasing rectangle for an arbitrary closed curve. Commun. ACM 18, 409-413 (1975) · Zbl 0308.68084
[39] Fukuda, K., Uno, T.: Polynomial time algorithms for maximizing the intersection volume of polytopes. Pac. J. Optim. 3(1), 37-52 (2007) · Zbl 1177.65087
[40] Graham, R.L., Lubachevsky, B.D., Nurmela, K.J., Östergård, P.R.J.: Dense packings of congruent circles in a circle. Discrete Math. 181(1-3), 139-154 (1998) · Zbl 0901.52017
[41] Heckmann, R., Lengauer, T.: Computing upper and lower bounds on textile nesting problems. Eur. J. Oper. Res. 108(3), 473-489 (1998) · Zbl 0943.90058
[42] Hershberger, J.: Finding the upper envelope of n line segments in O(nlogn) time. Inf. Process. Lett. 33(4), 169-174 (1989) · Zbl 0689.68058
[43] Löffler, M., van Kreveld, M.J.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom., Theory Appl. 43(4), 419-433 (2010) · Zbl 1208.65029
[44] Martin, R. R.; Stephenson, P. C., Containment algorithms for objects in rectangular boxes, 307-325 (1989), Berlin · Zbl 0716.68086
[45] Mattila, A.-L.: Piparikirja. Atena, Jyväskylä (2001). In Finnish · Zbl 1128.90048
[46] Medvedeva, A.; Mukhopadhyay, A., An implementation of a linear time algorithm for computing the minimum perimeter triangle enclosing a convex polygon, 25-28 (2003)
[47] Milenkovic, V., Translational polygon containment and minimal enclosure using linear programming based restriction, 109-118 (1996) · Zbl 0922.68129
[48] Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2d constructions. Comput. Geom., Theory Appl. 13(1), 3-19 (1999) · Zbl 0930.68152
[49] Mitchell, J.S.B., Polishchuk, V.: Minimum-perimeter enclosing k-gon. Inf. Process. Lett. 107(3-4), 120-124 (2008) · Zbl 1186.68509
[50] Mount, D.M., Silverman, R.: Minimum enclosures with specified angles. Technical Report CS-3219, University of Maryland, (1994)
[51] Mount, D.M., Silverman, R., Wu, A.Y.: On the area of overlap of translated polygons. Comput. Vis. Image Underst. 64(1), 53-61 (1996)
[52] Nurmela, K.J., Östergård, P.R.J.: More optimal packings of equal circles in a square. Discrete Comput. Geom. 22(3), 439-457 (1999) · Zbl 0931.05019
[53] O’Rourke, J.: Finding minimal enclosing boxes. Int. J. Comput. Inf. Sci. 14, 183-199 (1985) · Zbl 0582.68067
[54] Pirzadeh, H.: Computational geometry with the rotating calipers. Master’s thesis, McGill U (1999) · Zbl 1154.68544
[55] Schwarz, C.; Teich, J.; Vainshtein, A.; Welzl, E.; Evans, B. L., Minimal enclosing parallelogram with application, c34-c35 (1995)
[56] Skopenkov, M.: Packing a cake into a box. Am. Math. Mon. 118(5), 424-433 (2011) · Zbl 1218.52015
[57] Sugihara, K., Sawai, M., Sano, H., Kim, D.-S., Kim, D.: Disk packing for the estimation of the size of a wire bundle. Jpn. J. Ind. Appl. Math. 21, 259-278 (2004) · Zbl 1126.52300
[58] Toledo, S., Extremal polygon containment problems, 176-185 (1991), New York
[59] Toussaint, G. T., Solving geometric problems with the rotating calipers, 1-4 (1983)
[60] van Kreveld, M.J., Löffler, M.: Approximating largest convex hulls for imprecise points. J. Discrete Algorithms 6(4), 583-594 (2008) · Zbl 1154.68544
[61] Kreveld, M. J.; Speckmann, B.; Bose, P. (ed.); Morin, P. (ed.), Cutting a country for smallest square fit, Vancouver, BC, Canada, November 21-23, 2002, Berlin · Zbl 1019.68117
[62] van Lankveld, T., van Kreveld, M.J., Veltkamp, R.C.: Identifying rectangles in laser range data for urban scene reconstruction. Comput. Graph. 35(3), 719-725 (2011)
[63] Xu, Y.-C., Xiao, R.-B., Amos, M.:. Simulated annealing for weighted polygon packing. arXiv:0809.5005
[64] Yildirim, E.A.: On the minimum volume covering ellipsoid of ellipsoids. SIAM J. Optim. 17(3), 621-641 (2006) · Zbl 1128.90048
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.