22
$\begingroup$

Take some very small $\epsilon>0$, and consider the annulus/ring given by the set $\{(r,\theta)\ |\ 1-\epsilon\le r\le1\}\subset \mathbb{R}^2$.

We wish to place translated copies of this annulus down so that they cover the plane; obviously, this will cover some points multiple times, since the rings do not tile the plane without overlap. How can we do this to minimize the overall density, i.e., the number of times an average point is covered?

I can obtain a density of $\pi$ with the following construction (overlapping rings shown in darker shades):

enter image description here

However, it turns out this is suboptimal; we can do better by only placing $2/\epsilon$ of these rings in a line, and covering the plane with the resulting shapes:

enter image description here

This uses $2/\epsilon$ rings of area $2\pi\epsilon$ each, for a total area of $4\pi$, per $2\times 3$ rectangle in the tiling, so its density is $\frac{2\pi}3 \approx 2.094$.

We can improve this further by overlapping the above shapes vertically (as before, each of these is formed from $2/\epsilon$ rings):

enter image description here

A bit of calculus tells us this construction is optimized when the vertical overlap between two of the red regions is $2-\sqrt{\frac{3\sqrt{17}-5}2}$, for a total density of

$$\frac{\pi\sqrt{51\sqrt{17}-107}}{16}\approx 1.99954$$

Is this optimal? I'm curious about both improvements to this construction, and lower bounds that can be imposed on the density; so far I have not been able to establish lower bounds greater than $1$. Pointers to literature on this or related questions would also be welcome.

(It's fairly easy to show that a random point on a given annulus will be covered an average of at least $1+1/\pi$ times, but this oversamples multiply-covered points, so it doesn't tell us anything directly about the covering density.)

Improve this question
$\endgroup$
5
  • $\begingroup$ Originally posted at Math StackExchange here, with no progress on the question despite some interest. $\endgroup$
    – RavenclawPrefect
    Commented Jul 26, 2021 at 18:59
  • 1
    $\begingroup$ You could try a greedy algorithm: Start with one annulus. Find the point closest to the origin which is outside all the annuli so far. Cover that point with an appropriate annulus and repeat. Then at each stage, what is the covering density for the largest fully covered circle? Does that density seem to have a limit? $\endgroup$
    – user44143
    Commented Jul 26, 2021 at 22:20
  • $\begingroup$ @MattF.: "appropriate annulus" is hiding a fair bit of complexity there, I think. For instance, suppose that I try to minimize overlap with existing annuli while covering a point of minimum distance. Then if my currently-covered region is a disc centered at the origin, it will take infinitely many placements to cover the points just beyond the disc, since each new annulus gets placed tangent to the disc. Is there a particular algorithm for placing new annuli you had in mind? $\endgroup$
    – RavenclawPrefect
    Commented Jul 27, 2021 at 3:35
  • 1
    $\begingroup$ @MattF.: I tried this out using a discrete approximation to the plane with a fairly simple greedy algorithm: an annulus is lined up to the current closest uncovered point $P$, with its tangent line through $P$ altered by up to $0.1$ radians from the default setup (where it's perpendicular to the vector from the origin to $P$) to add some stochastic behavior. After placing $350$ annuli with thickness $0.1$ times the radius, the image looks like this, and its average density up to the radius covered so far is around $3.88$. $\endgroup$
    – RavenclawPrefect
    Commented Jul 27, 2021 at 6:12
  • $\begingroup$ I would center the first annulus at $(1-\epsilon, \epsilon)$ or the like, which probably leads to a unique choice at each step for the minimal point $p$ on the boundary of the union of the annuli. Then I would choose the next annulus to be tangent at $p$ to one of the previous annuli and so that the new union covers a neighborhood of $p$; there will be just a few options and the greedy choice is the one maximizing the newly covered area. $\endgroup$
    – user44143
    Commented Jul 27, 2021 at 7:56

0

Reset to default

You must log in to answer this question.