LIPIcs.ISAAC.2017.4.pdf
- Filesize: 0.68 MB
- 12 pages
Document
Placing your Coins on a Shelf
Authors
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
Cite As Get BibTex
Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn. Placing your Coins on a Shelf. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.4
Abstract
We consider the problem of packing a family of disks 'on a shelf,' that is, such that each disk touches the x-axis from above and such that no two disks overlap. We prove that the problem of minimizing the distance between the leftmost point and the rightmost point of any disk is NP-hard. On the positive side, we show how to approximate this problem within a factor of 4/3 in O(n log n) time, and provide an O(n log n)-time exact algorithm for a special case, in particular when the ratio between the largest and smallest radius is at most four.
Subject Classification
Keywords
- packing problems
- approximation algorithms
- NP-hardness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, and Fabian Stehn. Placing your coins on a shelf, 2017. URL: http://arxiv.org/abs/1707.01239.
-
Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. Unsolved Problems in Geometry. Springer-Verlag, 1991. pp. 108-110.
-
Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle packing for origami design is hard. In A. K. Peters, editor, Origami⁵: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010), pages 609-626, 2010.
- Christoph Dürr, Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez, and Gerhard Woeginger. The triangle scheduling problem. Journal of Scheduling, pages 1-8, 2017. URL: http://dx.doi.org/10.1007/s10951-017-0533-1.
-
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979.
- Thomas C. Hales, Mark Adams, Gertrud Bauer, Dat Tat Dang, John Harrison, Truong Le Hoang, Cezary Kaliszyk, Victor Magron, Sean McLaughlin, Thang Tat Nguyen, Truong Quang Nguyen, Tobias Nipkow, Steven Obua, Joseph Pleso, Jason Rute, Alexey Solovyev, An Hoai Thi Ta, Trung Nam Tran, Diep Thi Trieu, Josef Urban, Ky Khac Vu, and Roland Zumkeller. A formal proof of the Kepler conjecture. Forum of Mathematics, Pi, 5(e2):1-29, 2017. URL: http://dx.doi.org/10.1017/fmp.2017.1.
-
Thomas C. Hales and Samuel P. Ferguson. A formulation of the Kepler conjecture. Discrete & Computational Geometry, 36(1):21-69, 2006.
-
Johannes Kepler. Strena seu de nive sexangula (The six-cornered snowflake). 1611.
-
Boris Klemz, Martin Nöllenburg, and Roman Prutkin. Recognizing weighted disk contact graphs. In Graph Drawing and Network Visualization, volume 9411 of LNCS, pages 433-446. Springer, 2015.
- Eckehard Specht. www.packomania.com. Accessed 2017-06-28. URL: http://www.packomania.com/.
-
Yu. G. Stoyan and Georgiy Yaskov. A mathematical model and a solution method for the problem of placing various-sized circles into a strip. European Journal of Operational Research, 156(3):590-600, 2004.