does every unit length curve lie inside the semicircle?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

does every unit length curve lie inside the semicircle?

Postby >-) » Thu Mar 10, 2016 3:18 pm UTC

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.

BedderDanu
Posts: 39
Joined: Tue Jan 14, 2014 6:18 am UTC

Re: does every unit length curve lie inside the semicircle?

Postby BedderDanu » Thu Mar 10, 2016 10:02 pm UTC

What about on top of?

The line from (0,1) ends on the semicircle. Does that still count as inside?

User avatar
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?

Postby Xanthir » Thu Mar 10, 2016 10:32 pm UTC

Clearly yes, otherwise >-) would have already discovered it didn't work. (And neither would their other example, of putting any curve into a diameter-1 circle.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

BedderDanu
Posts: 39
Joined: Tue Jan 14, 2014 6:18 am UTC

Re: does every unit length curve lie inside the semicircle?

Postby BedderDanu » Thu Mar 10, 2016 10:58 pm UTC

... misread diameter as radius. Nevermind.

User avatar
Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby Flumble » Fri Mar 11, 2016 12:49 am UTC

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 zig-zag 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=√(x-x^2). And, as wolfram knows, ⅓sin(α) ≤ √(cos(α)-cos(α)^2)... so this fails to disprove your hypothesis.

User avatar
measure
Posts: 131
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: does every unit length curve lie inside the semicircle?

Postby measure » Fri Mar 11, 2016 3:51 am UTC

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 shortest-length curve that has this rectangle as its bounding box? Can this shortest-length 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)

madaco
Posts: 165
Joined: Sat Feb 13, 2010 11:25 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby madaco » Fri Mar 11, 2016 6:41 pm UTC

Here's an idea:

If a curve cannot be fit inside the semi-circle, 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 semi-circle 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 semi-circle such that more of it would be inside the semi-circle 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.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby Cradarc » Sat Mar 12, 2016 10:16 am UTC

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 (quarter-circle) sector BOC.
Due to symmetry, we can apply the same argument to arc AB and segment AO in the other quarter-circle.

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(p2 + q2) + sqrt((q-cos(t))2 + sin(t)2)
= sqrt(p2 + q2) + sqrt(q2 + 1 - 2q*cos(t))

length(P->R->Q) = sqrt(cos(t)2 + (p-sin(t))2) + sqrt(p2 + q2)
= sqrt(p2 + 1 - 2p*sin(t)) + sqrt(p2 + q2)

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 semi-circle. 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.

DavidSh
Posts: 217
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby DavidSh » Sat Mar 12, 2016 7:43 pm UTC

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 a-b, that is, with two sides parallel to a-b, and two sides orthogonal to a-b. if R is has length p (parallel to a-b) and width q (orthogonal to a-b), then I claim x is at least sqrt(p2+(2q)2)

S contains points on each of the four sides of R. Some of these may coincide. Apply the billiard-player'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 a-b 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(p2+(2q)2) <= 2, R will fit in a semicircle of diameter 2.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby Cradarc » Sat Mar 12, 2016 10:44 pm UTC

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.

DavidSh
Posts: 217
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: does every unit length curve lie inside the semicircle?

Postby DavidSh » Sat Mar 12, 2016 11:51 pm UTC

If you use that argument, you can't add the lengths from the two sectors together.

Consider the path e-f-g-h 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.

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: does every unit length curve lie inside the semicircle?

Postby ThirdParty » Sun Mar 13, 2016 6:02 am UTC

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 a-b, that is, with two sides parallel to a-b, and two sides orthogonal to a-b. if R is has length p (parallel to a-b) and width q (orthogonal to a-b), then I claim x is at least sqrt(p2+(2q)2)
I agree, and I accept your proof of that claim.

DavidSh wrote:Then we just need to show that for any p by q rectangle R, if sqrt(p2+(2q)2) <= 2, R will fit in a semicircle of diameter 2.
Which is easily done:
Spoiler:
Since sqrt(p2+(2q)2) <= 2, the line segment from (-0.5p,-q) to (0.5p,q) must have length no greater than 2, so the line segment from (0,0) to (0.5p,q) must have length no greater than 1. Ditto the line segment from (0,0) to (-0.5p,q).

So the p-by-q rectangle "-0.5p≤x≤0.5p; 0≤y≤q" is entirely contained by the semicircle of diameter 2 "sqrt(x2+y2)≤1; 0≤y".

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: does every unit length curve lie inside the semicircle?

Postby Derek » Mon Mar 14, 2016 3:04 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests