does every unit length curve lie inside the semicircle?
Moderators: gmalivuk, Moderators General, Prelates
does every unit length curve lie inside the semicircle?
Closely related to Moser's worm problem
Can every unit length curve in R² be rotated and translated to fit inside a semicircle with diameter 1?
If we use a circle with diameter 1 instead of a semicircle, this can be accomplished by placing the midpoint of the curve in the center of the circle. The same trick does not work for a semicircle, but it seems that I am still able to fit every curve one way or another.
I'm trying to find a unit length curve which cannot fit in the semicircle or a way to prove that every curve can fit.
Hints preferred to complete answers.
Can every unit length curve in R² be rotated and translated to fit inside a semicircle with diameter 1?
If we use a circle with diameter 1 instead of a semicircle, this can be accomplished by placing the midpoint of the curve in the center of the circle. The same trick does not work for a semicircle, but it seems that I am still able to fit every curve one way or another.
I'm trying to find a unit length curve which cannot fit in the semicircle or a way to prove that every curve can fit.
Hints preferred to complete answers.

 Posts: 39
 Joined: Tue Jan 14, 2014 6:18 am UTC
Re: does every unit length curve lie inside the semicircle?
What about on top of?
The line from (0,1) ends on the semicircle. Does that still count as inside?
The line from (0,1) ends on the semicircle. Does that still count as inside?
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: does every unit length curve lie inside the semicircle?
Clearly yes, otherwise >) would have already discovered it didn't work. (And neither would their other example, of putting any curve into a diameter1 circle.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 39
 Joined: Tue Jan 14, 2014 6:18 am UTC
Re: does every unit length curve lie inside the semicircle?
... misread diameter as radius. Nevermind.
Re: does every unit length curve lie inside the semicircle?
I don't know how to prove it, but fitting a curve in a convex object is the same as fitting the curve's convex hull. Something with the curve containing all extrema already and the hull not adding to that.
Consider a zigzag shape from left to right going slightly up, down and up again with an angle α (or alternatively, an angle of 180°2α between two segments). The convex hull of this curve is a parallelogram with sides of ⅔cos(α) and ⅓.
If you start with the long side on the baseline from the corner (0,0), the height of the Z shape/parallelogram is y=⅓sin(α) while the height of the semicircle at the rightmost location x=cos(α) is y=√(xx^2). And, as wolfram knows, ⅓sin(α) ≤ √(cos(α)cos(α)^2)... so this fails to disprove your hypothesis.
Consider a zigzag shape from left to right going slightly up, down and up again with an angle α (or alternatively, an angle of 180°2α between two segments). The convex hull of this curve is a parallelogram with sides of ⅔cos(α) and ⅓.
If you start with the long side on the baseline from the corner (0,0), the height of the Z shape/parallelogram is y=⅓sin(α) while the height of the semicircle at the rightmost location x=cos(α) is y=√(xx^2). And, as wolfram knows, ⅓sin(α) ≤ √(cos(α)cos(α)^2)... so this fails to disprove your hypothesis.
Re: does every unit length curve lie inside the semicircle?
Flumble wrote:I don't know how to prove it, but fitting a curve in a convex object is the same as fitting the curve's convex hull. Something with the curve containing all extrema already and the hull not adding to that.
I was thinking along the same lines. If we define the "bounding box" of a curve as the smallest rectangle that contains it, and consider the largest rectangle of a given aspect ratio that will fit in the semicircle (a set of semicyclic? rectangles from the degenerate segment on the diameter to a square with side length 2*sqrt(5)/5. For each of these rectangles, what is the shortestlength curve that has this rectangle as its bounding box? Can this shortestlength curve ever be longer than 1? (for a/b < 1/2, I believe the shortest necessary curve is the two segments from the midpoint of a long side to the two opposite corners)
Re: does every unit length curve lie inside the semicircle?
Here's an idea:
If a curve cannot be fit inside the semicircle, then for a given way of putting it on the semicircle, there is a related curve of the same length which meets the boundary of the semicircle at the same points (because the semi circle is convex).
It seems like either the result would be either be "stuck" if you confined it to the semi circle, or there would be another way to place the first curve on the semicircle such that more of it would be inside the semicircle before folding parts over.
So then, looking at curves of length 1 which are "stuck" when constrained to be in the semi circle seems like it could be useful.
For a curve with a length (not necessarily 1) , which is "stuck" any part of the curve can be changed except for the parts that are either on the boundary, or get arbitrarily close to the boundary (I think. I might be wrong about this, but I wouldn't think so.), and still result in a curve which is "stuck" when in the semi circle.
So, because how [the parts not on or near the boundary] are connected does not matter, those parts can all be made to be straight lines between places at or near the boundary (which would make the length of the curve shorter, unless they already are straight lines).
I'm less sure of this, but I don't think changing the order of the connections of these parts would change whether the curve was "stuck", and making the connections all go in the same order (e.g. all clockwise) would make the length of the curve shorter.
So, if this reasoning is correct, for any curve which has a length and is "stuck", there is one which is not longer which is "stuck" and has the same parts on the boundary.
So, if there is a curve of length 1 which is "stuck", there is one which is also of length 1 and "stuck" which is composed of parts near the boundary, connected in clockwise or counterclockwise order by straight lines.
I'm not sure, but I would guess that parts which are arbitrarily close to, but do not meet, the boundary, do not result in a shorter curve which is "stuck". (I don't think there is any benefit to having it get arbitrarily close without touching, I think it would make the curve longer without any added benefit.).
So, if there is a curve of length 1 which is "stuck", I think there is one which is composed of only arcs of the semi circle, intervals on the diameter, stray points on the boundary, and straight lines connecting these together.
Are there any collections of 3 points and connecting edges which would result in a stuck curve of length 1?
I think not really, or at least, not completely stuck. (Can rotate, but not move freely at all)
So, I think this might help?
If a curve cannot be fit inside the semicircle, then for a given way of putting it on the semicircle, there is a related curve of the same length which meets the boundary of the semicircle at the same points (because the semi circle is convex).
It seems like either the result would be either be "stuck" if you confined it to the semi circle, or there would be another way to place the first curve on the semicircle such that more of it would be inside the semicircle before folding parts over.
So then, looking at curves of length 1 which are "stuck" when constrained to be in the semi circle seems like it could be useful.
For a curve with a length (not necessarily 1) , which is "stuck" any part of the curve can be changed except for the parts that are either on the boundary, or get arbitrarily close to the boundary (I think. I might be wrong about this, but I wouldn't think so.), and still result in a curve which is "stuck" when in the semi circle.
So, because how [the parts not on or near the boundary] are connected does not matter, those parts can all be made to be straight lines between places at or near the boundary (which would make the length of the curve shorter, unless they already are straight lines).
I'm less sure of this, but I don't think changing the order of the connections of these parts would change whether the curve was "stuck", and making the connections all go in the same order (e.g. all clockwise) would make the length of the curve shorter.
So, if this reasoning is correct, for any curve which has a length and is "stuck", there is one which is not longer which is "stuck" and has the same parts on the boundary.
So, if there is a curve of length 1 which is "stuck", there is one which is also of length 1 and "stuck" which is composed of parts near the boundary, connected in clockwise or counterclockwise order by straight lines.
I'm not sure, but I would guess that parts which are arbitrarily close to, but do not meet, the boundary, do not result in a shorter curve which is "stuck". (I don't think there is any benefit to having it get arbitrarily close without touching, I think it would make the curve longer without any added benefit.).
So, if there is a curve of length 1 which is "stuck", I think there is one which is composed of only arcs of the semi circle, intervals on the diameter, stray points on the boundary, and straight lines connecting these together.
Are there any collections of 3 points and connecting edges which would result in a stuck curve of length 1?
I think not really, or at least, not completely stuck. (Can rotate, but not move freely at all)
So, I think this might help?
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.
Re: does every unit length curve lie inside the semicircle?
Building off of Madaco's idea...
Any unit length curve that won't fit can be placed in such a way so that the length that does fall inside the circle is maximized. Let's call it the "maximal contained curve" (MCC).
To make things easier, let me define a semicircle:
The semicircle is centered at the origin, O, with diameter AC. A = (1,0), C = (1,0). We construct a point B on the arc at (0,1). We also construct segment BO. An MCC for this semicircle is be formed by taking a particular curve of length 2 and maximizing the length of curve that is contained within the semicircle.
NOTE: My semicircle has diameter 2 to make the math less messy later on. I will be working with curves of length 2 so the argument scales to unit dimensions.
The MCC will intersect the boundary of this semicircle at a set of points.
Claim 1.a: At least one intersection point is on minor arc AB and minor arc BC, respectively.
Claim 1.b: At least one intersection point is on segments AO and OC, respectively.
Reasoning:
If there is no point of intersection on arc AB, the MCC can be shifted in the <1,1> direction
If there is no point of intersection on arc BC, the MCC can be shifted in the <1,1> direction
If there is no point of intersection on segment AO or OC, the MCC can be shifted in the <0,1> direction
If there is a point of intersection on exactly one of AO or OC, the MCC can be rotated about the origin.
In all of the above cases, the MCC can be moved to accommodate a longer length curve. This contradicts with the definition of the MCC.
Claim 2: Any MCC must cut through BO
Reasoning:
This follows directly from Claim 1 if the MCC is to be continuous. An MCC that is discontinuous would imply the continuity of the original curve must exist outside of the semicircle. It isn't hard to show that such a curve must have length > 2 using what we established in Claim 1.
Now let's consider a particular MCC which intersects BO at point P, arc BC at point R, and segment OC at point Q. Notice this effectively reduces the area of interest to the (quartercircle) sector BOC.
Due to symmetry, we can apply the same argument to arc AB and segment AO in the other quartercircle.
Claim 3: The length of the MCC contained in the sector BOC cannot be less than the shortest path that traverses P, Q,and R.
Reasoning:
The MCC is continuous so it must connect P, Q, and R. Any continuous curve connecting a series of points cannot be shorter than the shortest possible path traversing those points.
Claim 4: The length of the shortest path that traverses P, Q,and R is at least 1.
Reasoning:
Let P = (0,p), Q = (q,0), R = (cos(t),sin(t)).
Due to symmetry, P and Q are interchangeable. Thus we only have to consider the two paths: P>Q>R and P>R>Q.
length(P>Q>R) = sqrt(p^{2} + q^{2}) + sqrt((qcos(t))^{2} + sin(t)^{2})
= sqrt(p^{2} + q^{2}) + sqrt(q^{2} + 1  2q*cos(t))
length(P>R>Q) = sqrt(cos(t)^{2} + (psin(t))^{2}) + sqrt(p^{2} + q^{2})
= sqrt(p^{2} + 1  2p*sin(t)) + sqrt(p^{2} + q^{2})
Note that both path lengths are minimized when p,q > 0. The minimum value is 1.
Conclusion
Given any MCC, the curve length contained in an (arbitrarily selected) half of the semicircle is at least 1. This means the total MCC length is at least 2. However, our premise is that the MCC is constructed from a curve of length 2. Thus, every such MCC is in fact, the original curve. No part is ever excluded from the semicircle. So every curve with length 2 would fit inside my semicircle with diameter 2.
DISCLAIMER:This is far from a rigorous proof, but hopefully you can fill in arguments for some of the fringe cases I failed to cover.
Any unit length curve that won't fit can be placed in such a way so that the length that does fall inside the circle is maximized. Let's call it the "maximal contained curve" (MCC).
To make things easier, let me define a semicircle:
The semicircle is centered at the origin, O, with diameter AC. A = (1,0), C = (1,0). We construct a point B on the arc at (0,1). We also construct segment BO. An MCC for this semicircle is be formed by taking a particular curve of length 2 and maximizing the length of curve that is contained within the semicircle.
NOTE: My semicircle has diameter 2 to make the math less messy later on. I will be working with curves of length 2 so the argument scales to unit dimensions.
The MCC will intersect the boundary of this semicircle at a set of points.
Claim 1.a: At least one intersection point is on minor arc AB and minor arc BC, respectively.
Claim 1.b: At least one intersection point is on segments AO and OC, respectively.
Reasoning:
If there is no point of intersection on arc AB, the MCC can be shifted in the <1,1> direction
If there is no point of intersection on arc BC, the MCC can be shifted in the <1,1> direction
If there is no point of intersection on segment AO or OC, the MCC can be shifted in the <0,1> direction
If there is a point of intersection on exactly one of AO or OC, the MCC can be rotated about the origin.
In all of the above cases, the MCC can be moved to accommodate a longer length curve. This contradicts with the definition of the MCC.
Claim 2: Any MCC must cut through BO
Reasoning:
This follows directly from Claim 1 if the MCC is to be continuous. An MCC that is discontinuous would imply the continuity of the original curve must exist outside of the semicircle. It isn't hard to show that such a curve must have length > 2 using what we established in Claim 1.
Now let's consider a particular MCC which intersects BO at point P, arc BC at point R, and segment OC at point Q. Notice this effectively reduces the area of interest to the (quartercircle) sector BOC.
Due to symmetry, we can apply the same argument to arc AB and segment AO in the other quartercircle.
Claim 3: The length of the MCC contained in the sector BOC cannot be less than the shortest path that traverses P, Q,and R.
Reasoning:
The MCC is continuous so it must connect P, Q, and R. Any continuous curve connecting a series of points cannot be shorter than the shortest possible path traversing those points.
Claim 4: The length of the shortest path that traverses P, Q,and R is at least 1.
Reasoning:
Let P = (0,p), Q = (q,0), R = (cos(t),sin(t)).
Due to symmetry, P and Q are interchangeable. Thus we only have to consider the two paths: P>Q>R and P>R>Q.
length(P>Q>R) = sqrt(p^{2} + q^{2}) + sqrt((qcos(t))^{2} + sin(t)^{2})
= sqrt(p^{2} + q^{2}) + sqrt(q^{2} + 1  2q*cos(t))
length(P>R>Q) = sqrt(cos(t)^{2} + (psin(t))^{2}) + sqrt(p^{2} + q^{2})
= sqrt(p^{2} + 1  2p*sin(t)) + sqrt(p^{2} + q^{2})
Note that both path lengths are minimized when p,q > 0. The minimum value is 1.
Conclusion
Given any MCC, the curve length contained in an (arbitrarily selected) half of the semicircle is at least 1. This means the total MCC length is at least 2. However, our premise is that the MCC is constructed from a curve of length 2. Thus, every such MCC is in fact, the original curve. No part is ever excluded from the semicircle. So every curve with length 2 would fit inside my semicircle with diameter 2.
DISCLAIMER:This is far from a rigorous proof, but hopefully you can fill in arguments for some of the fringe cases I failed to cover.
This is a block of text that can be added to posts you make. There is a 300 character limit.
Re: does every unit length curve lie inside the semicircle?
I think the reasoning for Cradarc's Claim 3 is faulty.
Yes, the curve has to connect P, Q, and R, but you haven't shown that it has to do it within the sector.
I think the following approach works, extending measure's idea.
Let S be a curve of length x.
Let a and b be the two endpoints of S.
Let R be the minimal rectangle containing S, among those aligned to the line ab, that is, with two sides parallel to ab, and two sides orthogonal to ab. if R is has length p (parallel to ab) and width q (orthogonal to ab), then I claim x is at least sqrt(p^{2}+(2q)^{2})
S contains points on each of the four sides of R. Some of these may coincide. Apply the billiardplayer's trick of tiling the plane with reflected copies of R, to see that, no matter which order the sides are visited, the total length of S is as required. Use the fact that ab is parallel to the sides of R with length p.
(We can construct a path S^ which more clearly has the required length by traveling along S until the first of the four sides is reached, along the reflection S' of S over that side until the reflection of the next of the four sides is reached, along the reflection S" of S' over that second side, and so on along reflections S"' and S"", until the reflection b"" of b is reached. The distance of b"" from a is at least the required distance.)
Then we just need to show that for any p by q rectangle R, if sqrt(p^{2}+(2q)^{2}) <= 2, R will fit in a semicircle of diameter 2.
Yes, the curve has to connect P, Q, and R, but you haven't shown that it has to do it within the sector.
I think the following approach works, extending measure's idea.
Let S be a curve of length x.
Let a and b be the two endpoints of S.
Let R be the minimal rectangle containing S, among those aligned to the line ab, that is, with two sides parallel to ab, and two sides orthogonal to ab. if R is has length p (parallel to ab) and width q (orthogonal to ab), then I claim x is at least sqrt(p^{2}+(2q)^{2})
S contains points on each of the four sides of R. Some of these may coincide. Apply the billiardplayer's trick of tiling the plane with reflected copies of R, to see that, no matter which order the sides are visited, the total length of S is as required. Use the fact that ab is parallel to the sides of R with length p.
(We can construct a path S^ which more clearly has the required length by traveling along S until the first of the four sides is reached, along the reflection S' of S over that side until the reflection of the next of the four sides is reached, along the reflection S" of S' over that second side, and so on along reflections S"' and S"", until the reflection b"" of b is reached. The distance of b"" from a is at least the required distance.)
Then we just need to show that for any p by q rectangle R, if sqrt(p^{2}+(2q)^{2}) <= 2, R will fit in a semicircle of diameter 2.
Re: does every unit length curve lie inside the semicircle?
DavidSh wrote:I think the reasoning for Cradarc's Claim 3 is faulty.
Yes, the curve has to connect P, Q, and R, but you haven't shown that it has to do it within the sector.
We don't have to show it is contained in the sector because we are looking for the minimal length. A path that isn't contained in the sector will be longer than the minimal length. Suppose after connecting only two of the three points, the curve leaves the sector. That means the curve must intersect the boundary of the sector at a new point K. The shortest path from K to the remaining unconnected point will not leave the sector. So the minimum length of any such curve is the shortest path traversing Q,P,R,K, which lies completely within the sector.
In other words, if you can provide a solution where the curve leaves the sector, I can replace the part that loops out of the sector with a particular strip of the sector's boundary it bypasses. This will preserve all properties while reducing the length of the MCC.
This is a block of text that can be added to posts you make. There is a 300 character limit.
Re: does every unit length curve lie inside the semicircle?
If you use that argument, you can't add the lengths from the two sectors together.
Consider the path efgh defined as follows.
Let theta be some small positive angle.
Let e = (sin(theta), cos(theta)), f = (sin(theta),cos(theta)), g = (sin(theta),0), h = (sin(theta),0).
This has a point on each of the minor arcs AB and BC, and points on each of the segments BO and CO.
Its length in sector AOB is cos(theta)+2sin(theta), and its length in sector BOC is 2sin(theta),
for a total length of cos(theta)+4sin(theta), less than 2 for small theta.
It isn't a counterexample for >)'s conjecture, but it doesn't seem to fit with the argument with your claim 3 and conclusion.
Consider the path efgh defined as follows.
Let theta be some small positive angle.
Let e = (sin(theta), cos(theta)), f = (sin(theta),cos(theta)), g = (sin(theta),0), h = (sin(theta),0).
This has a point on each of the minor arcs AB and BC, and points on each of the segments BO and CO.
Its length in sector AOB is cos(theta)+2sin(theta), and its length in sector BOC is 2sin(theta),
for a total length of cos(theta)+4sin(theta), less than 2 for small theta.
It isn't a counterexample for >)'s conjecture, but it doesn't seem to fit with the argument with your claim 3 and conclusion.
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: does every unit length curve lie inside the semicircle?
I agree, and I accept your proof of that claim.DavidSh wrote:I think the following approach works, extending measure's idea.
Let S be a curve of length x.
Let a and b be the two endpoints of S.
Let R be the minimal rectangle containing S, among those aligned to the line ab, that is, with two sides parallel to ab, and two sides orthogonal to ab. if R is has length p (parallel to ab) and width q (orthogonal to ab), then I claim x is at least sqrt(p^{2}+(2q)^{2})
Which is easily done:DavidSh wrote:Then we just need to show that for any p by q rectangle R, if sqrt(p^{2}+(2q)^{2}) <= 2, R will fit in a semicircle of diameter 2.
Spoiler:
Re: does every unit length curve lie inside the semicircle?
Cradarc wrote:If there is no point of intersection on arc AB, the MCC can be shifted in the <1,1> direction
If there is no point of intersection on arc BC, the MCC can be shifted in the <1,1> direction
These two claims are incorrect, but can be salvaged. If you shift the curve in <1, 1> to touch arc AB, it is possible that you have moved some other segment of the curve outside of arc BC. However, you can shift the curve by <1, 0> instead. Likewise for the second claim.
DavidSh's objection is valid though. You've proven that the MCC must be continuous within the semicircle, but not within the quarter circle that you are investigating.
Who is online
Users browsing this forum: No registered users and 10 guests