Convex Polygons

[Orgasmic Troll]

Originally Posted by mfgoode

Well Davi you can see for your self. This problem is an excellent one given by Davar 55.

Its a general rule that original thinkers are never welcome anywhere.

Instead of using the poison pen try cracking this problem out for a change.

I have pondered it long and deep and tried to work it out but came to a conclusion that the inner perimeter turns out to be greater than the outer one ! so Im waiting for enlightenment from you.

Mally

Your tongue must double as a treadmill for all the times you put your foot in your mouth. I handed you THREE definitions of convex. I would really like to see you put forth just a little bit more effort so you can see why you are posting worthless crap. I can hand you the answer to why you're wrong, but call me Silverman, I want to see you do your homework.

[Orgasmic Troll]

Originally Posted by Zeta-Flux

Travis,

It is obvious you can rotate until Q bumps up against P at a second point. You just rotate the minimum amount until this happens. (If Q already intersects P at two points, or along a line, no rotation is necessary.)

I was going to leave it to the rest of you to figure out why this is beneficial. The reason is as follows.

Label all of the vertices of Q (along with all intersection points between P and Q--ignoring line segments in common). Then, given any two consecutive edges which are not colinear, you can force them to be colinear, by moving the middle vertex. This always results in a convex polygon with smaller perimeter. There are two cases.

1) Doing this straightening doesn't make Q hit P. In this case, the straightening reduces the number of vertices.

2) During the straightening process, Q hits P. Then the straightening has to stop, and there is a new intersection point between Q and P. One must show that only finitely many new vertices can be added in this way (left to the reader). Eventually, the edges of Q and the edges of P become common edges.

Thus, after a finite number of steps, the outer polygon is reduced to the smaller polygon, and the perimeter always lost length.

Cheers,
Zeta-Flux

P.S. A better way than translating and rotating, is just linearly reducing the entire perimeter of Q until it cannot be reduced further without going inside P (i.e. take the smallests polygon which is similar to Q, but also still able to contain P).

Zeta, you can do that process without moving Q at all and it will still work (btw, I've come over to your side, I agree you can translate and rotate Q to create at least 2 points of intersection. The counterexamples in my head were non-convex)

[mfgoode]

Originally Posted by Zeta-Flux

Fix any direction vector (or any line). One can translate Q along this vector (or line) the minimum distance until Q intersects P. This guarantees one point of intersection. Rotation about this point of intersection will guarantee a second (if it doesn't already exist).

Well lets look at it this way. Let the two p-gons be P and Q where Q is the outer one.

From a reference point inside both p-gons draw a ray intersecting both

Then the ray to Q is greater than to P Lets call the ray segments Rp and Rq.

Hence Rp < Rq

Call the perimeters Pp and Pq.

Lets say the Areas Ap and Aq are the perimeters times (x) some functions of the ray segments Ra and Rb.

Therefore Pp x f(Rp) < Rq x f(Rq)

But f(Rp) < f(Rq) .

From this data try working it out and see the conclusion. which of course is wrong. But where is the catch ?

Mally

[mfgoode]

I have noted the time of my post which is wrong. It says 6.18 p.m. where as here it is past midnight. Travis' post came minutes after I logged out but I received it by e-mail and it has not appeared here as yet

I appreciate your brushing up for my benefit and have seldom seen such a concise difinition of 'convex' Thats when I realised a Koch curve has both vertex angles acute and obtuse hence it does not qualify for this problem and my thanks go to you Travis for putting me right.

Mally

[davar55]

This is the argument I had in mind. I sure hope it's satisfactory.

If the containing polygon is the same as the contained polygon,
then the perimeters are equal as someone pointed out, but let's
assume that's not the case.

Then choose any side of the interior polygon that, when extended
as a line, divides the containing polygon into two regions, i.e any
side not co-linear with a side of the containing polygon. Now extend
this side, in one or both directions if necessary, until it
intersects the containing polygon.

Reduce the containing polygon by removing the region outside the
contained polygon sliced off by this line. The result is still convex,
and contains the original contained polygon, but has a smaller
perimeter, simply by the axiom that a straight line (segment) is the
shortest distance between two points. Here the straight line
segment is the extended side, and is shorter than the portion
of the perimeter of the containing polygon being removed.

Since the contained polygon has a finite number of sides, repeat
this reduction for each relevant side until the outer polygon is
reduced to the inner polygon. The perimeter is thus repeatedly
decreased, proving the original proposition.

[akruppa]

Neat. Looks good to me.

Alex

[R.D. Silverman]

Originally Posted by akruppa

Neat. Looks good to me.

Alex

A somewhat more sophisticated approach.

Suppose the interior polygon has N sides, the exterior M.

Suppose N < M. Add points to the interior polygon, such that the
added points lie on an edge so the interior polygon now has M
vertices. (some colinear) Consider both polygons embedded in E^M.
One can construct a pos. def. matrix that maps the interior polygon
to the exterior and this matrix has determinant > 1, [Why? The
larger polygon clearly has larger area; consider the Jacobian] Now note that
such a matrix maps line segments to line segments so that the new
line segments are at least as long as the old ones.

[Zeta-Flux]

Dear R.D. Silverman,

As it stands, there are a few holes in your method.

1. Part of the problem lies in the possibility that M<N.

2. One can choose a convex polygon Q containing another polygon P, both having the same number of sides and vertices, but with one of the sides of Q smaller than ALL the sides of P. So, your statement that all of the line segments are larger needs explication.

Cheers,
Zeta-Flux

[davieddy]

Originally Posted by mfgoode

I appreciate your brushing up for my benefit and have seldom seen such a concise difinition of 'convex' Thats when I realised a Koch curve has both vertex angles acute and obtuse hence it does not qualify for this problem and my thanks go to you Travis for putting me right.

Mally

It is the "reflex" internal angles which are the problem, not
the obtuse ones.

David

[Zeta-Flux]

davar55,

That is a slick proof.

[philmoore]

Originally Posted by Zeta-Flux

davar55,
That is a slick proof.

Yes, thanks for a nice problem!