×

Placing your coins on a shelf. (English) Zbl 1457.68273

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 4, 12 p. (2017).
Summary: 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.
For the entire collection see [Zbl 1376.68013].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms

Software:

kepler98
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Chris tian Knauer, and Fabian Stehn. Placing your coins on a shelf, 2017. arXiv:1707.01239.
[2] Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. {\it Unsolved Problems in Geom-} {\it etry}. Springer-Verlag, 1991. pp. 108-110. · Zbl 0748.52001
[3] Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle packing for origami design is hard. In A. K. Peters, editor, {\it Origami}5{\it : Proceedings of the 5th International Conference} {\it on Origami in Science, Mathematics and Education (OSME 2010)}, pages 609-626, 2010.
[4] Christoph Dürr, Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Ós car C. Vásquez, and Gerhard Woeginger. The triangle scheduling problem. {\it Journal of} {\it Scheduling}, pages 1-8, 2017. doi:10.1007/s10951-017-0533-1.
[5] Michael R. Garey and David S. Johnson. {\it Computers and Intractability: A Guide to the} {\it Theory of }NP{\it -Completeness}. W. H. Freeman & Co., New York, NY, USA, 1979. · Zbl 0411.68039
[6] 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. {\it Forum of Mathematics,} {\it Pi}, 5(e2):1-29, 2017. doi:10.1017/fmp.2017.1. · Zbl 1379.52018
[7] Thomas C. Hales and Samuel P. Ferguson. A formulation of the Kepler conjecture. {\it Discrete} {\it & Computational Geometry}, 36(1):21-69, 2006. · Zbl 1186.52014
[8] Johannes Kepler. {\it Strena seu de nive sexangula (The six-cornered snowflake)}. 1611.
[9] Boris Klemz, Martin Nöllenburg, and Roman Prutkin. Recognizing weighted disk contact graphs. In {\it Graph Drawing and Network Visualization}, volume 9411 of {\it LNCS}, pages 433-446. Springer, 2015. · Zbl 1471.68199
[10] Eckehard Specht.www.packomania.com.Accessed 2017-06-28.URL: http://www. packomania.com/.
[11] Yu. G. Stoyan and Georgiy Yaskov. A mathematical model and a solution method for the problem of placing various-sized circles into a strip. {\it European Journal of Operational} {\it Research}, 156(3):590-600, 2004. · Zbl 1056.90018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.