# Circle Packing for Origami Design Is Hard

• Published in 2010
In the collection
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 8/pi=2.546... These results are motivated by problems arising in the context of origami design.

## Other information

key
Demaine2010
type
article
2010-08-13
date_published
2010-02-02
journal
Arxiv preprint arXiv:1008.1224
pages
1--17
publisher
arxiv.org

### BibTeX entry

@article{Demaine2010,
key = {Demaine2010},
type = {article},
title = {Circle Packing for Origami Design Is Hard},
author = {Demaine, E.D. and Fekete, S.P. and Lang, R.J.},
abstract = {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 8/pi=2.546... These results are motivated by problems arising in the context of origami design.},
comment = {},
}