5
$\begingroup$

Let $C$ be a unit-radius circle in the plane. Suppose you have a total length $L$ of string available, and your task is to connect chords of $C$ using no more than $L$ of string to minimize the largest radius $r$ disk inside $C$ that can avoid all chords. So, if you have $L=4$, it is natural to $(+)$-partition $C$, which achieves $r=\sqrt{2}-1 \approx 0.414$, as illustrated left below.


      TangentDisks23
If you have as much as $L \approx 5.084$ string, then the three chords shown right above achieve $r \approx 0.309$. I have no principled reason to believe this is optimal for that $L$ (although you can see that I at least arranged the six disks to have the identical radius $r$).

The general question is:

Q1. For a given $L$, what is the smallest $r$ one can ensure by chords of $C$ whose total length is no more than $L$?

This might be approachable for small $L$, or by exploring a fixed number $n$ of chords ($n=2,3$ above). Perhaps Q2 is more tractable?

Q2. What is the optimal pattern of chords as $L$ grows large? Is it a non-equally-spaced orthogonal grid?

I have asked similar questions before: "Optimal planar net for catching convex shapes" and "Chord arrangement that avoids confining small or large disks." The tension here is that Yoav Kallus showed that the former question is answered by a hexagonal tiling, but straight chords cannot create such a tiling.


         


$\endgroup$
  • 3
    $\begingroup$ it seems to me you could do better if all chords are parallel. E.g. with $L=4$ (or even a bit less than that) you could place two horizontal chords at $y=\pm 1/3$ giving you $r=1/3$ better than $0.414$ $\endgroup$ – Mirko Nov 15 '14 at 2:27
  • $\begingroup$ @user48481MirkoSwirko: Nice observation! Perhaps parallel chords serve as the generic solution? $\endgroup$ – Joseph O'Rourke Nov 15 '14 at 2:29
  • $\begingroup$ Yes, I see now that my earlier question, "The sparsest planar net that captures every unit segment" excluded this possibility by focusing on the diameter of the "holes" in the net rather than the disk radii... $\endgroup$ – Joseph O'Rourke Nov 15 '14 at 2:42
4
$\begingroup$

Partial update: It is easier to find the minimum $L$ possible for a given $r.$ I take this approach more consistently in the second part. I conjecture that for fixed $r$ it is optimal to use parallel chords at $y=1-2r,1-4r,1-6r,\cdots,1-2kr$ stopping at $k=\lfloor \frac1r\rfloor.$

enter image description here

For $L \le 2,$ I can't see doing better than a single chord at $y=-\sqrt{1-\frac{L^2}{4}}$ allowing a radius of $$r=\frac{1+y}{2}=\frac{2+\sqrt{4-L^2}}4.$$

As L increases this moves up and at $L=2$ becomes a diameter at $y=0$ with $r=\frac12.$

As $L$ increases past $2$ we can obtain $r \lt \frac12$: A short chord at $y=1-4r$ accompanies the longer (but no longer quite as long) chord which is at $y=1-2r.$ So $$L=4(\sqrt{r-r^2}+\sqrt{2r-4r^2 }).$$ Eventually, as Mirko notes, we arrive at $r=\frac13$ with equal chords at $y=\pm \frac13$ and $$L=\frac{8\sqrt{2}}{3} \approx 3.771236.$$

For somewhat larger $L$ values we can make make $|y|$ slightly smaller ( so those two chords become slightly longer) and leave a small bit over for chords at $\pm 3y.$ By my calculation, at $L=4$ that gives $$r=y=\frac{\sqrt{2\sqrt{73}-10}}8\approx 0.3327914.$$

However, on more careful analysis, chords at $1-2r,1-4r,1-6r$ for $r\approx 0.332253809$ is better. The exact value is the root of a certain degree $6$ polynomial.

In your picture for $L \approx 5.084$ the vertical diameter helps somewhat but note how focussing on $r$ helps. Removing that vertical diameter but keeping the same $r$ necessitate moving the horizontal chords up slightly and adding another short one at the bottom. I (now) suspect that, for this $L$ and some larger ones, the pattern of chords at $1-2r,1-4r,1-6r$ remains optimal until $r=\frac14$ when $L=2+2\sqrt{3}\approx 5.4641.$ So with $L=5$ one gets $r \approx 0.299533.$


Somewhat more careful analysis:

We will include the possibility of single point chords (called trivial) to account for disks tangent to the unit circle. However we will ignore them except when needed to have statements make sense. A chord with center at $(a,b)$ has length $2\sqrt{1-a^2-b^2}.$ We will pick a convenient orientation without comment. For example we will use horizontal chords where possible. A set of chords partitions the interior of the unit circle into connected regions.

An $(L,r)-$configuration is a set of chords of combined length $L$ and disks all of radius $r$ with these properties:

  • The interior of each disk is disjoint from the chords.
  • No connected region can accommodate a disk of radius larger than $r.$
  • Each region which can contain a disk of radius $r$, actually does so.

We call this an optimal configuration if there is no $(L,r')-$configuration with $r' \gt r.$ The stated problem is to find this maximal $r$ given $L.$ It seems easier to use the equivalent condition that there is no $(L',r)$ configuration with $L' \lt L$ and hence to minimize $L$ given $r.$ Of course the optimal configurations and $(L,r)$ pairs are the same.

For example, as discussed above, for $\frac{1}{4} \le r \le \frac13$, chords at $y=1-2r,1-4r,1-6r$ give an $(L,r)-$configuration for $L=\,\sqrt {r-{r}^{2}}+4\,\sqrt {2\,r-4\,{r}^{2}}+4\,\sqrt {3\,r-9\,{r}^{2}}.$ This makes $r$ the larger real root of a degree $6$ polynomial $$(37748736+9437184L^2)r^6 +\cdots+L^8.$$ But that hardly seems helpful. I believe this is optimal.

Each disk $D$ in an $(L,r)-$configuration (optimal or otherwise) is tangent to two or more chords. Call this set of chords $s(D).$ Our conditions require that the points of tangency with $s(D)$ must contain the center of $D$ is in their convex hull. Note that with $3$ or more chords in $s(D)$, both the center and radius are fixed.

  • If $\frac12 \lt r \lt 1$ then there is just one disk,$D$. If $s(D)$ contains only two chords then they are $y=t$ and $y=t-2r$ for some $r \le t \le 1.$ A quick calculation shows that $t=1$ (only one non-trivial chord) is best. Note that if $D$ is tangent to the circle then this shortest non-trivial chord tangent to $D$ is all we need. I've convinced myself that at least three non-trivial cords in $s(D)$ is even worse. I won't spell out my laborious reasoning for this seemingly evident fact. So $L=2\sqrt{1-(1-2r)^2 }=4\sqrt{r-r^2}.$

  • For $\frac13 \lt r \lt \frac12$ more than one non-trivial chord will be needed. Two possible configurations are chords at $y=s$, $y=s-2r$ and $y=s-4r$ for some $1-2r \lt s \le 1$ with two regions allowing disks or chords at $y=s$ and $y=s-2r$ for some $r \lt s \lt 4r-1$ with only one region allowing disks. The first option with $s=1$ is best so this at least shows that $$L \le 4\sqrt{r-r^2}+4\sqrt{2r-4r^2}.$$ Again the only gap here is disposing of the case that some disk has three non-trivial chords in $s(D)$: If any disk has two chords in $s(D)$, both non-trivial, the given configuration is optimal. If two disks $D_1,D_2$ are tangent to the circle, there is no advantage to having more than one non-trivial cord in either $s(D_i).$

  • I won't say more about $\frac14 \lt r \lt \frac13$ than I already have.

This is a good way from a proof, but at least it gives a direction. As a moral argument, anything else wastes some length by fixing both the center and radius of some disk.

$\endgroup$
  • 2
    $\begingroup$ I agree with the above, though one may ask how to make a proof out of it. For $L=4$ following the same ideas I had come with $r=a/2$ where $3a+b=2$ and $\sqrt{1-(1-a)^2}+\sqrt{1-(1-a-b)^2}+\sqrt{1-(1-b)^2}=2$ which I did not solve exactly but plotted the graph (substituting $b=2-3a$) and read the $a$ coordinate from the graph, there were two of these but only the larger one seemed to make sense and it gave $r\approx0.3322538$ (which seems very slightly off the above answer, perhaps approximation error). $\endgroup$ – Mirko Nov 15 '14 at 13:46
  • $\begingroup$ Nice analysis. Not a proof, but it seems that parallel chords must be best. $\endgroup$ – Joseph O'Rourke Nov 15 '14 at 15:04
  • $\begingroup$ @Mirko You were right about $L=4.$ $\endgroup$ – Aaron Meyerowitz Nov 16 '14 at 6:57
  • $\begingroup$ Wow! $\mbox{}{} $ $\endgroup$ – Joseph O'Rourke Nov 16 '14 at 15:31

Your Answer

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

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