Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Graph Profile Realizations and Applications to Social Networks Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Efficient Algorithm for Box Folding

Authors : Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

For a given polygon P and a polyhedron Q, the folding problem asks if Q can be obtained from P by folding it. This simple problem is quite complicated, and there is no known efficient algorithm that solves this problem in general. In this paper, we focus on the case that Q is a box, and the size of Q is not given. That is, input of the box folding problem is a polygon P, and it asks if P can fold to boxes of certain sizes. We note that there exist an infinite number of polygons P that can fold into three boxes of different sizes. In this paper, we give a pseudo polynomial time algorithm that computes all possible ways of folding of P to boxes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Matching Sets of Line Segments
next chapter Analyzing the Quantum Annealing Approach for Solving Linear Least Squares Problems
Footnotes
1
We do not give the formal definition of curvature. Intuitively, it indicates the quantity of paper around the point measured by its angle. See [6] for further details.
 
2
For sake of simplicity, we do not define the labels of points in P on an edge shared by two rectangles of Q. We also do not define the label of a point p corresponding to the vertex \(v_i\) of Q.
 
3
Some readers may consider the first phase is enough. However, we have not yet checked if some particles of polygons cause overlap on a face of Q. In other words, we have to check each face is made by particles of polygons by gluing without overlap or hole.
 
4
The number of polyomino of area 30 is 2368347037571252.
 
Literature
1.
2.
Akiyama, J.: Tile-Makers and Semi-Tile-Makers. The Mathematical Association of Amerika, Monthly 114, pp. 602–609, August–September 2007
3.
Akiyama, J., Nara, C.: Developments of polyhedra using oblique coordinates. J. Indonesia. Math. Soc. 13(1), 99–114 (2007)MathSciNetCrossRef
4.
Bobenko, A.I., Izmestiev, I.: Alexandrov’s theorem, weighted Delaunay triangulations, and mixed volumes. Annales de l’Institut Fourier 58(2), 447–505 (2008)MathSciNetCrossRef
5.
Buchin, K., et al.: On rolling cube puzzles. In: 19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 141–144 (2007)
6.
Demaine, E.D., O’Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, New York (2007)CrossRef
7.
Dürer, A.: Underweysung der messung, mit den zirckel un richtscheyt, in Linien ebnen unnd gantzen corporen (1525)
8.
Horiyama, T., Mizunashi, K.: Folding orthogonal polygons into rectangular boxes. In: Proceedings of the 19th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2016) (2016)
9.
10.
Mitani, J., Uehara, R.: Polygons folding to plural incongruent orthogonal boxes. In: Canadian Conference on Computational Geometry (CCCG 2008), pp. 39–42 (2008)
11.
Shirakawa, T., Uehara, R.: Common developments of three incongruent orthogonal boxes. Int. J. Comput. Geom. Appl. 23(1), 65–71 (2013)MathSciNetCrossRef
12.
Xu, D., Horiyama, T., Shirakawa, T., Uehara, R.: Common developments of three incongruent boxes of area 30. Comput. Geom. Theory Appl. 64, 1–17 (2017)MathSciNetCrossRef
Metadata
Title
Efficient Algorithm for Box Folding
Authors
Koichi Mizunashi
Takashi Horiyama
Ryuhei Uehara
Copyright Year
2019
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-10563-1

Electronic ISBN: 978-3-030-10564-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-10564-8_22

Premium Partner

    Image Credits