Placing your Coins on a Shelf

Authors Helmut Alt, Kevin Buchin, Steven Chaplick, Otfried Cheong, Philipp Kindermann, Christian Knauer, Fabian Stehn



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.4.pdf
  • Filesize: 0.68 MB
  • 12 pages

Document Identifiers

Author Details

Helmut Alt
Kevin Buchin
Steven Chaplick
Otfried Cheong
Philipp Kindermann
Christian Knauer
Fabian Stehn

Cite AsGet 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.
Keywords
  • packing problems
  • approximation algorithms
  • NP-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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.
  2. Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy. Unsolved Problems in Geometry. Springer-Verlag, 1991. pp. 108-110. Google Scholar
  3. 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. Google Scholar
  4. 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.
  5. 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. Google Scholar
  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. Forum of Mathematics, Pi, 5(e2):1-29, 2017. URL: http://dx.doi.org/10.1017/fmp.2017.1.
  7. Thomas C. Hales and Samuel P. Ferguson. A formulation of the Kepler conjecture. Discrete & Computational Geometry, 36(1):21-69, 2006. Google Scholar
  8. Johannes Kepler. Strena seu de nive sexangula (The six-cornered snowflake). 1611. Google Scholar
  9. 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. Google Scholar
  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. European Journal of Operational Research, 156(3):590-600, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail