Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Nice! So for one disk of diameter $1$, the integral is $\pi$. –  Joseph O'Rourke Jun 11 at 10:50
1  
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). –  Jan Kyncl Jun 12 at 4:30
    
And for four discs, there are a continuum many configurations where the integral is $\pi +4$. –  Jan Kyncl Jun 13 at 4:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.