The disk
covering problem
In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems ...
asks for the smallest
real number such that
disks of radius
can be arranged in such a way as to cover the
unit disk
In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1:
:D_1(P) = \.\,
The closed unit disk around ''P'' is the set of points whose di ...
. Dually, for a given radius ''ε'', one wishes to find the smallest integer ''n'' such that ''n'' disks of radius ''ε'' can cover the unit disk.
[.]
The best solutions known to date are as follows.
Method
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.
[ The corresponding angles θ are written in the "Symmetry" column in the above table.
]
References
External links
*
* Finch, S. R. "Circular Coverage Constants." §2.2 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 484–489, 2003.
Discrete geometry
Covering problems
{{geometry-stub