4
$\begingroup$

Suppose we are given an infinite sequence $(\mathbf{r}_n)_{n=1}^\infty$ of 2D points, spread uniformly over space, with a given density $\rho$.

What is the supremum of the percentage of surface covered by the circles with centers $\mathbf{r}_n$ and radii $a_n$, such that the circles do not overlap?

The answer will obviously not depend on the sequence $(\mathbf{r}_n)_{n=1}^\infty$. I also think that $\rho$ will just become a multiplicative constant.

Clarification:

$(\mathbf{r}_n)_{n=1}^\infty$ is a fixed sequence of 2D points distributed uniformly (constant density) over the 2 dimensional plane. Not all sequences of radii $(a_n)_{n=1}^\infty$ are such that the circles do not overlap, but some do. Therefore, the supremum over this set of the percentage of the plane covered by the circles exists. My question is whether this percentage can be calculated or how to approach this problem.

An image is worth a thousand words:

Since the 2D surface is infinitely large, no probability theory is required and the solution will not depend on $(\mathbf{r}_n)_{n=1}^\infty$.

Image for explanation

Problem statement as a limit, ($\rho=1$ for simplicity):

Given $N$ uniformly distributed random 2D vectors on a square of size $\sqrt{N}\times\sqrt{N}$, called $\mathbf{r}_1,\cdots,\mathbf{r}_N$. Define:

$$f(\mathbf{r}_1,\cdots,\mathbf{r}_N)=\sup_{a_1,\cdots,a_N}\left\{\frac{1}{\underbrace{N}_{\text{total area}}}\underbrace{\sum_{i=1}^N\pi a_i^2}_{\text{filled area}}:\underbrace{\forall i\forall j\neq i:\|\mathbf{r}_i-\mathbf{r}_j\|\leq a_i+a_j}_{\text{no circles overlap}}\right\}$$

What is $\lim_{N\to\infty}f(\mathbf{r}_1,\cdots,\mathbf{r}_N)$?

I hope everybody agrees that this number will not depend on the choice of $(\mathbf{r}_n)_{n=1}^\infty$, since the 2D surface is infinitely large, but I am afraid my question is ill-posed (does taking the $\mathbb{E}$ help?).

$\endgroup$
  • 2
    $\begingroup$ I am not sure the problem is well defined. Say we just have three points. How do you determine the radius around each point? You could have a circle around one that almost touches the nearest, then small circles around the others or you could have medium sized circles around each one. The first will lead to larger total area. $\endgroup$ – Ross Millikan Apr 25 '18 at 18:29
  • $\begingroup$ I agree with Ross Millikan. Consider this example: if you take a center $r_n$ at every point with rational coordinates, it's impossible to place a disk with positive radius with no overlapping. Because rational numbers are dense in $\mathbb R$, any disk with positive radius has to contain another center. To avoid overlapping, you end up with a collection of singletons whose surface area is 0. I don't think that is what you're interested in, so you probably want to specify in more detail the constraints on $r_n$, $a_n$, and $\rho$. $\endgroup$ – N.Bach Apr 26 '18 at 12:32
  • $\begingroup$ After re-reading more carefully, I guess that what you had in mind would be something like a point lattice, in which case this problem is related to circle packing. And in that case, the optimal configuration in the plane is obtained for an hexagonal lattice/grid. $\endgroup$ – N.Bach Apr 26 '18 at 12:43
  • $\begingroup$ @RossMillikan, the problem is well-defined: the supremum exists, because it is bounded by 100%. $\endgroup$ – Carucel Apr 26 '18 at 20:15
  • $\begingroup$ @N.Bach, I am not allowed to choose the $\mathbf{r}_n$'s, only to choose the radii, i.e., the $a_n$'s. $\endgroup$ – Carucel Apr 26 '18 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.