Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing

See http://en.wikipedia.org/wiki/Ginger_biscuit

See http://www.annasthins.ca/

See http://en.wikipedia.org/wiki/Cat_flap

See http://pack-any-shape.com/

Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606–635 (2004)

Agarwal, P.K., Sharir, M.: Davenport-Schinzel sequences and their geometric applications. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 1–47. Elsevier Science/North-Holland, Amsterdam (2000)

Ahn, H.-K., Bae, S.W., Cheong, O., Gudmundsson, J., Tokuyama, T., Vigneron, A.: A generalization of the convex Kakeya problem. In: Fernández-Baca, D. (ed.) Theoretical Informatics—10th Latin American Symposium (LATIN 2012), Arequipa, Peru, April 16–20, 2012. Lecture Notes in Computer Science, vol. 7256, pp. 1–12. Springer, Berlin (2012)

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)

Ahn, H.-K., Cheng, S.-W., Reinbacher, I.: Maximum overlap of convex polytopes under translation. Comput. Geom., Theory Appl. 46(5), 552–565 (2013)

Ahn, H.-K., Cheong, O.: Stacking and bundling two convex polygons. In: Algorithms and Computation, 16th International Symposium (ISAAC 2005), Sanya, Hainan, China, December 19–21 (2005)

Ahn, H.-K., Cheong, O.: Aligning two convex figures to minimize area or perimeter. Algorithmica 62(1–2), 464–479 (2012)

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)

Alt, H., Blömer, J., Wagener, H.: Approximation of convex polygons. In: Paterson, M. (ed.) Proc. Automata, Languages and Programming, 17th International Colloquium (ICALP 1990), Warwick University, England, July 16–20, 1990. Lecture Notes in Computer Science, vol. 443, pp. 703–716. Springer, Berlin (1990)

Alt, H., Fuchs, U., Rote, G., Weber, G.: Matching convex shapes with respect to the symmetric difference. Algorithmica 21(1), 89–103 (1998)

Alt, H., Hurtado, F.: Packing convex polygons into rectangular boxes. In: Akiyama, J., Kano, M., Urabe, M. (eds.) Discrete and Computational Geometry, Japanese Conference, JCDCG 2000, Tokyo, Japan, November, 22–25 Lecture Notes in Computer Science, vol. 2098, pp. 67–80. Springer, Berlin (2000). Revised Papers

Aonuma, H., Imai, H., Imai, K., Tokuyama, T.: Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams. In: Proc. 6th Annual Symposium on Computational Geometry, pp. 225–234. ACM, New York (1990)

Arkin, E.M., Efrat, A., Hart, G., Kostitsyna, I., Kröller, A., Mitchell, J.S.B., Polishchuk, V.: Scandinavian thins on top of cake: on the smallest one-size-fits-all box. In: Kranakis, E., Krizanc, D., Luccio, F.L. (eds.) Proc. Fun with Algorithms—6th International Conference, FUN 2012, Venice, Italy, June 4–6, 2012. Lecture Notes in Computer Science, vol. 7288, pp. 16–27. Springer, Berlin (2012)

Arkin, E.M., Khuller, S., Mitchell, J.S.B.: Geometric knapsack problems. Algorithmica 10, 399–427 (1993)

Avnaim, F., Boissonnat, J.-D.: Simultaneous containment of several polygons. In: Proc. 3rd Annual Symposium on Computional Geometry, pp. 242–250 (1987)

Baker, B.S., Fortune, S.J., Mahaney, S.R.: Polygon containment under translation. J. Algorithms 7, 532–548 (1986)

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)

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)

Bhattacharya, B.K., Mukhopadhyay, A.: On the minimum perimeter triangle enclosing a convex polygon. In: Akiyama, J., Kano, M. (eds.) JCDCG’02. Lecture Notes in Computer Science, vol. 2866, pp. 84–96. Springer, Berlin (2003)

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)

Boyce, J.E., Dobkin, D.P., Drysdale, R.L. III, Guibas, L.J.: Finding extremal polygons. SIAM J. Comput. 14, 134–147 (1985)

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. In: COCOON 2004. LNCS, vol. 3106, pp. 259–267. Springer, Berlin (2004)

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)

Chan, T.M.: Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom., Theory Appl. 35(1–2), 20–35 (2006)

Chang, J.S.: Polygon optimization problems. Report 240. CS, NYU, New York (1986)

Chang, J.S., Yap, C.K.: A polynomial solution for the potato-peeling problem. Discrete Comput. Geom. 1, 155–182 (1986)

Chazelle, B.M.: The polygon containment problem. Adv. Comput. Res. 1, 1–33 (1983)

Daniels, K., Milenkovic, V.J.: Multiple translational containment, Part I: An approximate algorithm. Algorithmica 19(1–2), 148–182 (1997)

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)

de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)

DePano, N.A.A.: Polygon approximation with optimized polygonal enclosures: applications and algorithms. Ph.D. thesis, Department of Computer Science, Johns Hopkins University (1987)

DePano, N.A.A., Aggarwal, A.: Finding restricted k-envelopes for convex polygons. In: Procedings of the 22nd Allerton Conference on Communication, Control, and Computing, pp. 81–90 (1984)

Egeblad, J., Nielsen, B.K., Brazil, M.: Translational packing of arbitrary polytopes. Comput. Geom., Theory Appl. 42(4), 269–288 (2009)

Freeman, H., Shapira, R.: Determining the minimum-area encasing rectangle for an arbitrary closed curve. Commun. ACM 18, 409–413 (1975)

Fukuda, K., Uno, T.: Polynomial time algorithms for maximizing the intersection volume of polytopes. Pac. J. Optim. 3(1), 37–52 (2007)

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)

Heckmann, R., Lengauer, T.: Computing upper and lower bounds on textile nesting problems. Eur. J. Oper. Res. 108(3), 473–489 (1998)

Hershberger, J.: Finding the upper envelope of n line segments in O(nlogn) time. Inf. Process. Lett. 33(4), 169–174 (1989)

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)

Martin, R.R., Stephenson, P.C.: Containment algorithms for objects in rectangular boxes. In: Theory and Practice of Geometric Modeling, pp. 307–325. Springer, Berlin (1989)

Mattila, A.-L.: Piparikirja. Atena, Jyväskylä (2001). In Finnish

Medvedeva, A., Mukhopadhyay, A.: An implementation of a linear time algorithm for computing the minimum perimeter triangle enclosing a convex polygon. In: Proc. Canadian Conference on Computational Geometry (CCCG 2003), pp. 25–28 (2003)

Milenkovic, V.: Translational polygon containment and minimal enclosure using linear programming based restriction. In: Proc. 28th Annual ACM Symposum on the Theory of Computing, pp. 109–118 (1996)

Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2d constructions. Comput. Geom., Theory Appl. 13(1), 3–19 (1999)

Mitchell, J.S.B., Polishchuk, V.: Minimum-perimeter enclosing k-gon. Inf. Process. Lett. 107(3–4), 120–124 (2008)

Mount, D.M., Silverman, R.: Minimum enclosures with specified angles. Technical Report CS-3219, University of Maryland, (1994)

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)

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)

O’Rourke, J.: Finding minimal enclosing boxes. Int. J. Comput. Inf. Sci. 14, 183–199 (1985)

Pirzadeh, H.: Computational geometry with the rotating calipers. Master’s thesis, McGill U (1999)

Schwarz, C., Teich, J., Vainshtein, A., Welzl, E., Evans, B.L.: Minimal enclosing parallelogram with application. In: Proc. 11th Annual Symposium on Computational Geometry, pp. C34–C35 (1995)

Skopenkov, M.: Packing a cake into a box. Am. Math. Mon. 118(5), 424–433 (2011)

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)

Toledo, S.: Extremal polygon containment problems. In: SoCG ’91, pp. 176–185. ACM, New York (1991)

Toussaint, G.T.: Solving geometric problems with the rotating calipers. In: Proceedngs of IEEE MELECON ’83, pp. 1–4 (1983)

van Kreveld, M.J., Löffler, M.: Approximating largest convex hulls for imprecise points. J. Discrete Algorithms 6(4), 583–594 (2008)

van Kreveld, M.J., Speckmann, B.: Cutting a country for smallest square fit. In: Bose, P., Morin, P. (eds.) Algorithms and Computation, 13th International Symposium (ISAAC 2002), Vancouver, BC, Canada, November 21–23, 2002. Lecture Notes in Computer Science, vol. 2518, pp. 91–102. Springer, Berlin (2002)

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)

Xu, Y.-C., Xiao, R.-B., Amos, M.:. Simulated annealing for weighted polygon packing. arXiv:0809.5005

Yildirim, E.A.: On the minimum volume covering ellipsoid of ellipsoids. SIAM J. Optim. 17(3), 621–641 (2006)