Circle Packing for Origami Design Is Hard
- Published in 2010
- Added on
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.
Links
Other information
- key
- Demaine2010
- type
- article
- date_added
- 2010-08-13
- date_published
- 2010-12-07
- 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 = {}, date_added = {2010-08-13}, date_published = {2010-12-07}, urls = {http://arxiv.org/abs/1008.1224,http://arxiv.org/pdf/1008.1224v2}, collections = {Geometry}, url = {http://arxiv.org/abs/1008.1224 http://arxiv.org/pdf/1008.1224v2}, journal = {Arxiv preprint arXiv:1008.1224}, pages = {1--17}, publisher = {arxiv.org}, year = 2010, urldate = {2010-08-13}, archivePrefix = {arXiv}, eprint = {1008.1224} }