iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00224-013-9493-9
Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

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

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Notes

  1. We reported our results in the conference versions [15, 17].

  2. This special case is very important in practice for those of us who have many laptops, and are wondering what should be the smallest bag into which any of the laptops can be put.

  3. Recall that we also extend \(w^{\min }_{I}(l) \) beyond \(\textrm {Dom}\,w^{\square}_{I} \) with the constant values of +∞ and L; hence, we obtain the additional segments in the graph of \(w^{\min }_{I}(l) \) that run outside \(\textrm {Dom}\,w^{\square}_{I} \).

  4. A more direct proof of the linear bound on the number of contact events would involve charging an event to the feature of A or B that disappears at the event from the pair (a t ,b t ); once disappeared, the feature never returns to the pair. With such a proof, we would additionally have to argue that the contact events can be discovered one-by-one, “on-the-fly” during the rotation, between the neighboring vertex events; a constant-time implementation of such a discovery is straightforward.

References

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

  2. See http://www.annasthins.ca/

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

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

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

    Article  MATH  MathSciNet  Google Scholar 

  6. 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)

    Chapter  Google Scholar 

  7. 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)

    Chapter  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  10. 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)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  13. 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)

    Chapter  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  15. 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

    Chapter  Google Scholar 

  16. 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)

    Chapter  Google Scholar 

  17. 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)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  23. 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)

    Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  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)

    Article  MATH  Google Scholar 

  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)

    Article  MATH  Google Scholar 

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

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  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. In: Procedings of the 22nd Allerton Conference on Communication, Control, and Computing, pp. 81–90 (1984)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  Google Scholar 

  44. 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)

    Chapter  Google Scholar 

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

  46. 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)

    Google Scholar 

  47. 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)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

  55. 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)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  61. 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)

    Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank the FUN’2012 Program Committee member for the suggestion to include a recipe for Scandinavian thins into the full version of the paper. The main ingredient for preparing the thins is honey: to have the thins baked, approach your spouse with “It’s been a long time since we had thins; would you mind baking them, honey?”. For those who want to prepare the biscuits alone, see for example [45].

We thank the anonymous referees for their helpful comments. E. Arkin and J. Mitchell are partially supported by the National Science Foundation (CCF-1018388). F. Hurtado is partially supported by projects MICINN MTM2009-07242, Gen. Cat. DGR2009SGR1040, and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306. V. Polishchuk is supported by the Academy of Finland grant 1138520 and the Research Funds of the University of Helsinki.

Author information

Authors and Affiliations

  1. Institut für Informatik, Freie Universität, Berlin, Germany

    Helmut Alt

  2. Applied Mathematics and Statistics, Stony Brook University, Stony Brook, USA

    Esther M. Arkin & Joseph S. B. Mitchell

  3. Computer Science, The University of Arizona, Tucson, USA

    Alon Efrat

  4. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain

    Ferran Hurtado

  5. Computer Science, Stony Brook University, Stony Brook, USA

    Irina Kostitsyna

  6. Computer Science, Technische Universität Braunschweig, Braunschweig, Germany

    Alexander Kröller

  7. Helsinki Institute for IT, Computer Science, University of Helsinki, Helsinki, Finland

    Valentin Polishchuk

Authors
  1. Helmut Alt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Esther M. Arkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alon Efrat
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. George Hart
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ferran Hurtado
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Irina Kostitsyna
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Alexander Kröller
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Joseph S. B. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Valentin Polishchuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Valentin Polishchuk.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alt, H., Arkin, E.M., Efrat, A. et al. Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing. Theory Comput Syst 54, 689–714 (2014). https://doi.org/10.1007/s00224-013-9493-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-013-9493-9

Keywords

Search

Navigation