Placing your coins on a shelf
| Autor: | Alt, Helmut, Buchin, Kevin, Chaplick, Steven, Cheong, Otfried, Kindermann, Philipp, Knauer, Christian, Stehn, Fabian, Okamoto, Yoshio, Tokuyama, Takeshi |
|---|---|
| Přispěvatelé: | Algorithms, Geometry and Applications |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences 000 Computer science knowledge general works Computational Geometry Metric Geometry (math.MG) Packing problems Approximation algorithms Mathematics - Metric Geometry Computer Science Metric Geometry NP-hardness FOS: Mathematics Computer Science - Computational Geometry Astrophysics::Earth and Planetary Astrophysics |
| Zdroj: | BASE-Bielefeld Academic Search Engine Maastricht University Journal of Computational Geometry, 9(1), 312-327. Macodrum library, Carleton University arXiv. Cornell University Library ISSUE=1707.01239;TITLE=arXiv 28th International Symposium on Algorithms and Computation (ISAAC 2017), 92, 4:1-4:12 Journal of Computational Geometry, 9(1), 312-327. Carleton University |
| ISSN: | 1920-180X |
| Popis: | 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 study the problem of minimizing the distance between the leftmost point and the rightmost point of any disk in such a packing. We show how to approximate this problem within a factor of 4/3 in O(n log n) time. We further provide an O(n log n)-time exact algorithm for a special case which includes inputs where the ratio between the largest radius and the smallest radius is less than four. On the negative side, we prove that the problem is NP-hard even when the ratio between the largest radius and the smallest radius is at most 36. Journal of Computational Geometry, Vol. 9 No. 1 (2018) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|