16
$\begingroup$

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.

What is the radius of the smallest disk that can contain (cover) all segments?

For $n=3$ it is clear that the equilateral triangle with $r=\dfrac1{\sqrt{3}}$ is best possible.
But already for $n=4$, we can do better than a square, by shifting two perpendicular segments as shown on the left below and placing the two other ones at small distances parallel to them. So we can realize $r={\sqrt{\dfrac38}}+\epsilon< \dfrac1{\sqrt{2}}$.
Likewise for $n=5$, where the three black edges of the pentagon can be moved inside such that the whole fits in the blue circle with diameter $\dfrac{\sqrt{5}+1}2$, thus $r=\dfrac{\sqrt{5}+1}4<\sqrt{\dfrac{5+\sqrt{5}}{10}}$ (the circumradius of the pentagon, orange circle). And there is still room for improvement, as the blue circle can be made smaller after pushing one of the grey segments diagonally upwards.
enter image description here
For even $n$, the segments come in pairs of same slope, so it makes sense to ignore one of each pair. Then e.g. for $n=4$, there is no need for epsilons or $r_{inf}$, and we can state $r_{min}={\sqrt{\dfrac38}}$. Further, $n=6$ reduces to the $n=3$ case.
For $n>6$, the unit circle does the job for a star-like constellation, shifting each segment in a way that $O$ is one of its endpoints. (Well, it also does it for smaller $n$, but worse than the above constructions.)

Is $r=1$ best possible for $n\ge7$? And what is $r_{min}$ for $n=5$?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Imagine the letters T and V typed into the same spot (and that the sides of the V make a right angle). This configuration shows that $r_{min} \leq \sqrt{1/2}$ for $n = 8$. $\endgroup$
    – Will Brian
    Commented Nov 3, 2015 at 15:32
  • $\begingroup$ @WillBrian Right. I start wondering if the optimal constructions for even $n$ are very different of the ones for odd $n$. $\endgroup$
    – Wolfgang
    Commented Nov 3, 2015 at 15:36
  • $\begingroup$ Possibly. It's not too hard to show (generalizing the $n = 8$ picture) that you can always do better than $r = 1$ for even $n$. $\endgroup$
    – Will Brian
    Commented Nov 3, 2015 at 15:38
  • 1
    $\begingroup$ For sure $r<0.99$ for any $n$. $\endgroup$
    – Anton Petrunin
    Commented Nov 3, 2015 at 17:20
  • $\begingroup$ For n=5, the small partial trapezoid pictured can include a fourth edge, and the minimal radius should reduce to a nice search. It will be slightly larger than sin(pi/5), but not by much, and may be smaller than the 0.685 I claimed elsewhere. Gerhard "After Five, Then Comes Seven" Paseman, 2015.11.06 $\endgroup$
    – Gerhard Paseman
    Commented Nov 6, 2015 at 18:11

5 Answers 5

Reset to default
11
$\begingroup$

Start by arranging all the segments into a single unit-radius half-disk. Then cut a wedge of about $39$ degrees and slide it down along with its contents as in the figure. You did not cut or rotate any of the segments and the circumscribing circle has radius of about $0.94$.

enter image description here

Improve this answer
$\endgroup$
7
  • $\begingroup$ Why 39 degrees? $\endgroup$
    – j.c.
    Commented Nov 3, 2015 at 20:22
  • 2
    $\begingroup$ I played around with the numbers by hand, but to optimize this construction you want the bottom edge of the blue wedge to be a chord of the circumcircle and the bottom-right point of the blue wedge to have a tangent parallel to its top edge. You can also improve (I think) by cutting another small wedge from the other end of the red wedge and putting it in the empty space above the red wedge. $\endgroup$
    – Yoav Kallus
    Commented Nov 3, 2015 at 20:26
  • $\begingroup$ This is a more compact version of the stacking idea I posted. Using your visualization, I think you can find a specific value of n_0 (and a few more cuts of the red piece) such that for all n > n_0 the required radius is a value less than 0.9. Gerhard "Or At Least Ten Elevenths" Paseman, 2015.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 3, 2015 at 20:43
  • 1
    $\begingroup$ Based on this construction, we may formulate a similar question independent of $n$ (or more precisely: fitting all $n$): How to cut a half unit disk into a number of wedges that can be re-arranged (by translations) to fit into the smallest possible disk? It looks like the optimal solution(s) of this are highly asymmetric! $\endgroup$
    – Wolfgang
    Commented Nov 3, 2015 at 20:52
  • $\begingroup$ @Wolfgang Sure. You may also allow point reflections (rotations by 180 degrees) of the wedges. $\endgroup$
    – Yoav Kallus
    Commented Nov 3, 2015 at 22:16
3
$\begingroup$

(This should be rather a comment to Yoav's answer, but a picture says more than 1000 comments.)

What about talking the two wedges and splitting the blue one into smaller wedges as shown, starting at the bottom and pushing each part rightmost against the circle? The result will be best if the blue parts have infinitesimally small angles. The blue area would then fill an area of $\pi/4$ between the circle on the right and a smooth curve obeying a certain differential equation on the left, which depends only on $r$ and the angle of the wedge (for which I have chosen 90° here). The angle and $r$ would then have to be optimized under the condition that there remains just enough space for the red wedge, probably as a whole.
I guess this is close to Gerhard's most recent idea. The missing link: finding the equation of that curve or at least some bounds...

EDIT: Thanks to Will Brian for alluding to the tractrix. After calculations by Robert Bryant in the tractrix thread, for an angle of 90° this construction can be done with $r\approx 0.8250033$ - which is within Gerhard Paseman's estimated range.
Of course the question remains whether 90° is best. enter image description here

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ The curve should be something like a tractrix. For a normal tractrix, we imagine ourselves dragging something on a string while walking along a straight line; for this curve, we're walking around a circle instead. $\endgroup$
    – Will Brian
    Commented Nov 5, 2015 at 20:11
  • $\begingroup$ I've managed to convince myself that for n=5, R_min is less than 0.7, through a non-tractrix construction. For a nonoptimal construction with r=0.698 nearly, take a gray edge from the pentagon and translate it inside the black three-sided trapezoid. One sees that there is room to push things around for a smaller circumscribing circle. Based on the tightness of this, I suspect R_min is greater than 2/3 for n=5 and for n greater than 7. Gerhard "Glad To See Tractrix Number" Paseman, 2015.11.09 $\endgroup$
    – Gerhard Paseman
    Commented Nov 9, 2015 at 17:58
  • $\begingroup$ @GerhardPaseman Have you done some trig or high precision drawing to come up with 3 decimals? Or have you instructed some program to use only non-overlapping segments and circles? $\endgroup$
    – Wolfgang
    Commented Nov 9, 2015 at 18:59
  • $\begingroup$ All work by hand, with a cheat at the end. I got r^2 = 1/4 + (1.5 tan 18)^2 with 18 being degrees, since the circle circumscribes the larger partial trapezoid. The calculator tells me r is about 0.698 . I could have made a mistake, but the pictures suggest a value near 0.7 to me. Gerhard "Feel Free To Correct Me" Paseman, 2015.11.09 $\endgroup$
    – Gerhard Paseman
    Commented Nov 9, 2015 at 19:04
  • $\begingroup$ This approach suggests a try at a good lower bound for arbitrary n. One needs to pack two near T's with one edge being a proper chord and all other edges being on the same side of that chord. It may not be tight, but I am basing my 2/3 estimate on an incomplete argument using these four edges. Gerhard "Likes To Use Suggestive Mathematics" Paseman, 2015.11.09 $\endgroup$
    – Gerhard Paseman
    Commented Nov 9, 2015 at 19:09
2
$\begingroup$

Indeed you can do better than r=1. The small and even cases are handled in the post, so I focus on the case of an odd number of sides.

Instead of arranging sides in a star, arrange them in a fan or in open pages of a book, taking up less than a semicircle (semidisk?). Move the horizontal edge down near the bottom out of the way. Split the remaining edges in half, each occupying a quarter disk. Ease one of the quarter disks down slightly, and the other quarter disk toward the center.

As n gets large, not much movement will be available, but more than 0. ( For large n, less than .01 this way. Sorry, Anton.)

Gerhard "Exact Radius Will Cost More" Paseman, 2015.11.03

Improve this answer
$\endgroup$
4
  • $\begingroup$ One can also consider a camera shutter construction, or pinwheel (extend each edge in one direction, clockwise or ccw). I don't feel like doing that algebra though. Gerhard "Maybe Anton Will Do It" Paseman, 2015.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 3, 2015 at 17:46
  • $\begingroup$ Ok, I'll do the geometry, and others can do the trig. Consider translating the top horizontal edge down and to the right to be a right side radius. Somewhere (maybe halfway) in between is where it should stop. This will give a small and maybe optimal value. I don't know yet if it will be less than 1. Gerhard "Needs More Coffee For Trigonometry" Paseman, 2015.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 3, 2015 at 17:53
  • $\begingroup$ Ok, fine. cos($\pi/n$). Gerhard "Double Check My Work Please" Paseman, 2015.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 3, 2015 at 18:01
  • $\begingroup$ Yes I have just found the same minimum for the camera shutter construction. $\endgroup$
    – Wolfgang
    Commented Nov 3, 2015 at 18:03
2
$\begingroup$

Here is a variant on Will Brian's idea, but inspired by the fan arrangement in the other answer.

As before, we treat only odd n, arrange them in a fan, but now we start moving the edges to the bottom. The horizontal edge is the bottommost edge, the next edge with least positive slope goes above this segment and slightly to the right (so its midpoint is above and to the right of the midpoint of the horizontal segment), its mirror image above and slightly to the left. As above, I won't do the algebra, but I imagine at least n/4 of the edges can be stacked this way before reaching the top half of the semicircle, leaving a depression into which the rest of the edges can sink. I suspect for n=7 one can beat the cosine pi/7 value reached by the pinwheel construction.

Gerhard "Don't Close The Suitcase Yet!" Paseman, 2015.11.03

Improve this answer
$\endgroup$
1
$\begingroup$

(This should be a comment on Wolfgang's answer/comment, but there's too much to say.) Consider unit length chords approaching the center of a circle of radius $r$. The chord part would actually be longer than unit length, but we will have endpoints lie on other chords.

Suppose we start with one chord below the circle at a distance of $-y_0$, so we are dealing with chords at the bottom. The new chord to be stacked has an endpoint on the current chord and makes an angle $\alpha$ with the current chord, and is pushed so that its other endpoint lies on the circle, so the chord intercepts the circle at abscissa $y_1 = y_0 + \sin \alpha$ . However, we are interested in how far this chord is from the center, so we rotate the whole diagram by $\alpha$ to make the new chord horizontal. This gives $y_2 = y_1\cos \alpha - \sqrt{r^2 - (y_1)^2}\sin \alpha$, so this second chord is at distance $-y_2 \lt -y_0$ from the circle center.

Starting with $y_0= -\sqrt{r^2 - 1/4}$, we iterate this for $\alpha=\pi/n$, giving a construction similar to the camera shutter but here the chords go only halfway around and are at different distances from the center of the circle. For those wishing to investigate further, iterate for $n-1$ times the map $$f_{r,n}(x) = x\cos \pi/n + \frac{\sin 2\pi/n}{2} - r \sin \pi/n \sqrt{1 - \big(\frac{x + \sin \pi/n}{r}\big)^2},$$ starting with values of $r$ near $0.94$ (thanks to Yoav Kallus). I suspect for $n=5$ we can get $r_{min}$ below $0.8$.

Gerhard "Round And Round We Go" Paseman, 2015.11.05

Improve this answer
$\endgroup$
4
  • $\begingroup$ On further consideration, it looks like r could be chosen not much larger than r satisfying r_0 + sqrt((r_0)^2 - 1/4) greater than (sin a)(1 + cos a + cos 2a + ... + cos (n-2)a) for a= pi/n. (Actually, it needs to be greater by a small amount depending on n, but this shows a lower bound for r for this construction.) Gerhard "Definitely Needs Someone Else Checking" Paseman, 2015.11.05 $\endgroup$
    – Gerhard Paseman
    Commented Nov 5, 2015 at 20:26
  • $\begingroup$ Using this method, I believe $r_{min} \lt 0.78$ for $n=5$. Verfication would be nice. Also, contrasting this with the other suggested method (interleaving book pages instead of doing a partial camera shutter) would be nice, in which case vary $\alpha$ from $\pi/n$ to $(n-2)\pi/n$ in steps of $\pi/n$, although stopping early is allowed. It might help to note that the case $n=4$ can't be beat, and that all other $n$ need stricty greater $r$. Gerhard "More Than I Will Do" Paseman, 2015.11.05 $\endgroup$
    – Gerhard Paseman
    Commented Nov 5, 2015 at 21:15
  • $\begingroup$ Also, once $r_{min}$ has been established for a few small odd integers $n$ (say $5,7,9$), then that can be used to estimate $r_{min}$ for larger $n$ as they will have edges close to those for the small integers, close enough that likely one can show their minimum radii are strictly greater. Gerhard "Should Have Seen This Already" Paseman, 2015.11.05 $\endgroup$
    – Gerhard Paseman
    Commented Nov 5, 2015 at 22:22
  • $\begingroup$ I think $r_{min}$ for $n=5$ is half of the long side of a triangle with sides $1,\phi=0.618..$ and included angle $4\pi/5$, which is a little more than $0.685$. For larger $n$ I conjecture $r_{min}$ is in $[0.7,0.85]$. Gerhard "Can't Be Too Far Wrong" Paseman, 2015.11.05. $\endgroup$
    – Gerhard Paseman
    Commented Nov 5, 2015 at 22:52

You must log in to answer this question.

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