Abstract | ||
---|---|---|
We consider the problem of determining the minimum number Nd of unit disks that is required to block all rays emanating from a point P in the two-dimensional space, where each disk has at least a distance d to point P and to any other disk. We study the asymptotic behavior of Nd, as d tends to infinity. By deriving upper bounds and lower bounds, we prove that pi2/16 infinity} N_d/d2 2, where the upper bound is based on establishing an interesting link between unit disks positioned on a regular triangular grid and Farey sequences from number theory. By positioning point P as well as the centers of the disks on the grid points of such a triangular grid, we create hexagonal rings of disks around P. We prove that we need exactly d-1 of these hexagons to block all rays emanating from P. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1145/1542362.1542394 | Symposium on Computational Geometry 2013 |
Keywords | DocType | Citations |
blocking set | Conference | 1 |
PageRank | References | Authors |
0.43 | 2 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nataša Jovanoviū | 1 | 1 | 0.43 |
Jan Korst | 2 | 175 | 19.94 |
Ramon Clout | 3 | 14 | 1.63 |
V. Pronk | 4 | 54 | 8.29 |
Ludo Tolhuizen | 5 | 166 | 134.16 |