Circle Packing for Origami Design Is Hard

• Published in 2010
• Added on 2010-08-13

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

• http://arxiv.org/abs/1008.1224
• http://arxiv.org/pdf/1008.1224v2

Other information

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}
}