2010/08/06 by Erik D. Demaine, Demaine, Erik D., Sandor P. Fekete +3
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #cs.CC #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1008.1224
17 pages, 13 figures. An abstract was presented at the 5th International Conference on Origami in Science, Mathematics and Education (5OSME). Updated to fix a numerical typo related to Figure 13, and a new result
arxiv created 2010/09/20 · arxiv updated 2010/09/21
We show that deciding whether a given set of circles can be packed into a rectangle, an equilateral triangle, or a unit square are NP-hard problems, settling the complexity of these natural packing problems. On the positive side, we show that any set of circles of total area 1 can be packed into a square of size 4/√(pi)=2.2567... These results are motivated by problems arising in the context of origami design.