Disk covering problem: Difference between revisions
Content deleted Content added
No edit summary |
|||
| (31 intermediate revisions by 20 users not shown) | |||
| Line 1: | Line 1: | ||
| ⚫ | The '''disk [[covering problem]]''' asks for the smallest [[real number]] <math>r(n)</math> such that <math>n</math> [[disk (mathematics)|disks]] of radius <math>r(n)</math> can be arranged in such a way as to cover the [[unit disk]]. Dually, for a given radius ''ε'', one wishes to find the smallest integer ''n'' such that ''n'' disks of radius ''ε'' can cover the unit disk.<ref>{{citation |
||
The '''disk covering problem''' was proposed by [[C. T. Zahn]] in 1962. |
|||
| last = Kershner | first = Richard |
|||
| journal = American Journal of Mathematics |
|||
| mr = 0000043 |
|||
| pages = 665–671 |
|||
| title = The number of circles covering a set |
|||
| volume = 61 |
|||
| year = 1939 |
|||
| issue = 3 |
|||
| doi=10.2307/2371320| jstor = 2371320 |
|||
}}.</ref> |
|||
The best solutions known to date are as follows.<ref name=CirclesCoveringCircles>{{cite web |url=https://erich-friedman.github.io/packing/circovcir/|title=Circles Covering Circles|last=Friedman|first=Erich|access-date=4 October 2021}}</ref> |
|||
| ⚫ | |||
{| class="wikitable" border="1" |
|||
| ⚫ | |||
|- |
|||
! n |
|||
! r(n) |
|||
! Symmetry |
|||
|- |
|||
| 1 |
|||
| 1 |
|||
| All |
|||
|- |
|||
| 2 |
|||
| 1 |
|||
| All (2 stacked disks) |
|||
|- |
|||
| 3 |
|||
| <math>\sqrt{3}/2</math> = 0.866025... |
|||
| 120°, 3 reflections |
|||
|- |
|||
| 4 |
|||
| <math>\sqrt{2}/2</math> = 0.707107... |
|||
| 90°, 4 reflections |
|||
|- |
|||
| 5 |
|||
| 0.609382... {{OEIS2C|A133077}} |
|||
| 1 reflection |
|||
|- |
|||
| 6 |
|||
| 0.555905... {{OEIS2C|A299695}} |
|||
| 1 reflection |
|||
|- |
|||
| 7 |
|||
| <math>1/2</math> = 0.5 |
|||
| 60°, 6 reflections |
|||
|- |
|||
| 8 |
|||
| 0.445041... |
|||
| ~51.4°, 7 reflections |
|||
|- |
|||
| 9 |
|||
| 0.414213... |
|||
| 45°, 8 reflections |
|||
|- |
|||
| 10 |
|||
| 0.394930... |
|||
| 36°, 9 reflections |
|||
|- |
|||
| 11 |
|||
| 0.380083... |
|||
| 1 reflection |
|||
|- |
|||
| 12 |
|||
| 0.361141... |
|||
| 120°, 3 reflections |
|||
|} |
|||
==Method== |
|||
* Weisstein, Eric W. "Disk Covering Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DiskCoveringProblem.html |
|||
The following picture shows an example of a dashed disk of radius 1 covered by six solid-line disks of radius ~0.6. One of the covering disks is placed central and the remaining five in a symmetrical way around it. |
|||
[[File:DiscCoveringExample.svg]] |
|||
While this is not the best layout for r(6), similar arrangements of six, seven, eight, and nine disks around a central disk all having same radius result in the best layout strategies for r(7), r(8), r(9), and r(10), respectively.<ref name=CirclesCoveringCircles/> The corresponding angles θ are written in the "Symmetry" column in the above table. |
|||
==References== |
|||
{{reflist}} |
|||
| ⚫ | |||
*{{MathWorld |title=Disk Covering Problem |id=DiskCoveringProblem}} |
|||
* Finch, S. R. "Circular Coverage Constants." §2.2 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 484–489, 2003. |
|||
| ⚫ | |||
[[Category:Discrete geometry]] |
[[Category:Discrete geometry]] |
||
[[Category: |
[[Category:Covering problems]] |
||
[[ko:원판 덮기 문제]] |
|||
| ⚫ | |||
Latest revision as of 20:09, 4 October 2021
The disk covering problem asks for the smallest real number such that disks of radius can be arranged in such a way as to cover the unit disk. Dually, for a given radius ε, one wishes to find the smallest integer n such that n disks of radius ε can cover the unit disk.[1]
The best solutions known to date are as follows.[2]
| n | r(n) | Symmetry |
|---|---|---|
| 1 | 1 | All |
| 2 | 1 | All (2 stacked disks) |
| 3 | = 0.866025... | 120°, 3 reflections |
| 4 | = 0.707107... | 90°, 4 reflections |
| 5 | 0.609382... OEIS: A133077 | 1 reflection |
| 6 | 0.555905... OEIS: A299695 | 1 reflection |
| 7 | = 0.5 | 60°, 6 reflections |
| 8 | 0.445041... | ~51.4°, 7 reflections |
| 9 | 0.414213... | 45°, 8 reflections |
| 10 | 0.394930... | 36°, 9 reflections |
| 11 | 0.380083... | 1 reflection |
| 12 | 0.361141... | 120°, 3 reflections |
Method
[edit]The following picture shows an example of a dashed disk of radius 1 covered by six solid-line disks of radius ~0.6. One of the covering disks is placed central and the remaining five in a symmetrical way around it.
While this is not the best layout for r(6), similar arrangements of six, seven, eight, and nine disks around a central disk all having same radius result in the best layout strategies for r(7), r(8), r(9), and r(10), respectively.[2] The corresponding angles θ are written in the "Symmetry" column in the above table.
References
[edit]- ^ Kershner, Richard (1939), "The number of circles covering a set", American Journal of Mathematics, 61 (3): 665–671, doi:10.2307/2371320, JSTOR 2371320, MR 0000043.
- ^ a b Friedman, Erich. "Circles Covering Circles". Retrieved 4 October 2021.
External links
[edit]- Weisstein, Eric W. "Disk Covering Problem". MathWorld.
- Finch, S. R. "Circular Coverage Constants." §2.2 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 484–489, 2003.
 | This geometry-related article is a stub. You can help Wikipedia by expanding it. |