6
$\begingroup$

Suppose one has $k$ unit-radius disks, and the goal is to hide them inside a disk of radius $R \gg k$. The detection probes are rays along a line. (Think of the disks as tumor cells, and the rays as radiation.)

Q1. What is the optimal hiding configuration for $k$ disks?

That is, how can the $k$ disks be arranged to be difficult to detect by ray probes?

I believe the probability of detection from, say, random ray probes, would be proportional to the integral, over all directions $\theta \in [0,\pi)$, of the measure of the projection/shadow of the disks in direction $\theta$. So I seek a configuration with the smallest mean shadow.

For example, it seems that for $k=3$, the obvious is the optimal configuration:

      Disks3Projection
But it is unclear to me if the optimal configuration under this projection-based integral measure is identical to, say, (a) the optimal packing of $k$ disks in a surrounding disk of minimal radius, or (b) the packing of $k$ disks with the minimum area convex hull.

Q2. Is the projection integral measure identical to any of the well-known, previously studied disk packing constraints?

Or perhaps what I am suggesting has already been studied on its own, in which case a pointer would be appreciated—thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Q2: If the union of the discs is conected, or more generaly, if no line separates the discs in a nontrivial way, then the integral of the lengths of the projections over $[0, \pi)$ is equal to the perimeter of the convex hull of the union of the discs. See, for example, Lemma 1 in this paper on opaque sets, where a related problem is studied.

It can be proved by approximating the perimeter by a polygonal curve and integrating each edge separately.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice! So for one disk of diameter $1$, the integral is $\pi$. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 11, 2014 at 10:50
  • 1
    $\begingroup$ Now for two such touching discs, the integral is $\pi + 2$, and for three discs like on the picture the integral is $\pi + 3$. Asymptotically, and approximately, it seems you want to pack the discs into another disc of smallest diameter (and thus perimeter). $\endgroup$
    – Jan Kyncl
    Commented Jun 12, 2014 at 4:30
  • $\begingroup$ And for four discs, there are a continuum many configurations where the integral is $\pi +4$. $\endgroup$
    – Jan Kyncl
    Commented Jun 13, 2014 at 4:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .