Page 1 of 1

Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 7:06 pm UTC
by aleph_one
Here's a fact that seems obvious, but took me a long time to find a proof.
Problem wrote:If a convex polygon A lies within a convex polygon B, then the perimeter of A is at most that of B.

I know two nice proofs of this, both pretty clever. One of them extends to the natural higher-dimensional generalization.

(This is kind-of a puzzle, but I think this subforum is more apt for it than Logic Puzzles.)

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 9:59 pm UTC
by letterX
How about: Pick a point C in the interior of the inner polygon. Draw rays from C to each of the vertices of the inner polygon. Because both the polygons are convex, and C is in the interior of both, each ray intersects each polygon exactly once.

Now, consider two adjacent rays, [imath]R_1, R_2[/imath] passing through the vertices [imath]v_1, v_2[/imath] of the inner polygon. Since they are adjacent rays, [imath](v_1, v_2)[/imath] is an edge of the inner polygon, and has length [imath]d(v_1, v_2)[/imath] (d is distance in the plane). Now, the rays [imath]R_1, R_2[/imath] intersect the outer polygon at points [imath]w_1, w_2[/imath] respectively (these points may not be vertices of the outer polygon, but we don't care). Since the outer polygon is outside the inner polygon, [imath]w_1[/imath] is further away from C than [imath]v_1[/imath], and similarly for [imath]w_2, v_2[/imath]. So, do some algebra and trigonometry to see that the straight line distance between [imath]w_1[/imath] and [imath]w_2[/imath] is at least [imath]d(v_1, v_2)[/imath]. But then, if we look at the distance along the perimeter of the outer polygon from [imath]w_1[/imath] to [imath]w_2[/imath], this is at least the straight line distance, hence is at least [imath]d(v_1, v_2)[/imath] as well. So, for each of these wedges, the perimeter of the outer polygon within this wedge is at least as large as the perimeter of the inner polygon within the wedge, and summing up over all the wedges, we account for the entire perimeter of both.

Doesn't really generalize to multiple dimensions (and generalized surface area, I presume you mean).

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 10:55 pm UTC
by antonfire
letterX wrote:How about: Pick a point C in the interior of the inner polygon. Draw rays from C to each of the vertices of the inner polygon. Because both the polygons are convex, and C is in the interior of both, each ray intersects each polygon exactly once.

Now, consider two adjacent rays, [imath]R_1, R_2[/imath] passing through the vertices [imath]v_1, v_2[/imath] of the inner polygon. Since they are adjacent rays, [imath](v_1, v_2)[/imath] is an edge of the inner polygon, and has length [imath]d(v_1, v_2)[/imath] (d is distance in the plane). Now, the rays [imath]R_1, R_2[/imath] intersect the outer polygon at points [imath]w_1, w_2[/imath] respectively (these points may not be vertices of the outer polygon, but we don't care). Since the outer polygon is outside the inner polygon, [imath]w_1[/imath] is further away from C than [imath]v_1[/imath], and similarly for [imath]w_2, v_2[/imath]. So, do some algebra and trigonometry to see that the straight line distance between [imath]w_1[/imath] and [imath]w_2[/imath] is at least [imath]d(v_1, v_2)[/imath].
This need not be true. Take C=0, v1=w1=(1,0), v2=(t,t2), w2=(1,t) for small t.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 11:07 pm UTC
by mmmcannibalism
I think the proof for regular polygons is that a regular polygon inscribed in a circle will have less perimeter then the circle*; and a circle inscribed in a regular polygon will have less perimeter then the polygon**. Generalize circle to infinigon and you have a proof for all regular polygons.

However, I don't know how to generalize this to non regular polygons.

*because circles use perimeter to make area more efficiently

**its intuitive, I'll write the formal proof up if I get time.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 11:10 pm UTC
by stephentyrone
mmmcannibalism wrote:I think the proof for regular polygons is that a regular polygon inscribed in a circle will have less perimeter then the circle*; and a circle inscribed in a regular polygon will have less perimeter then the polygon**. Generalize circle to infinigon and you have a proof for all regular polygons.


This doesn't get you there, because the larger polygon can be smaller than the smallest circle that circumscribes the smaller polygon.

I can see a couple ways to prove this, but both are fairly technical and brute force-y. Option one is to describe an algorithm that transforms the larger polygon into the smaller one, such that each step of the algorithm necessarily decreases the perimeter or leave it unchanged (not hard, but a little bit fussy). Option two would be to use the formula for arc length in polar coordinates:
[math]P = \int \sqrt{r^2 + \left(\frac{dr}{d\theta}\right)^2}d\theta[/math]
Use the fact that r of the larger polygon is always at least as large as r of the smaller polygon, and the convexity of the polygons gives you some bound on the integral of the square of [imath]\frac{dr}{d\theta}[/imath]; I believe that with some carefully chosen integral inequalities one could push this through, but it's an awful lot of machinery to prove such a simple and obvious fact.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 11:29 pm UTC
by heyitsguay
Let the vertices of the inner polygon be [imath]x_1,x_2,\ldots,x_n[/imath], so that there is an edge [imath]e_{i,i+1}[/imath] for all [imath]i\in[1,n-1][/imath] and an edge [imath]e_{n,1}[/imath]. Pick some point [imath]p[/imath] in the interior of the smaller polygon, and draw rays from [imath]p[/imath] to each [imath]x_i[/imath], letting the rays go on to intersect the larger polygon. Each two successive such rays isolate an edge [imath]e_{i,i+1}[/imath] from the rest of the interior polygon, and also isolate some subset of the boundary of the larger polygon from the rest of that boundary. Call the subset isolated in this way [imath]E_{i,i+1}[/imath], corresponding to [imath]e_{i,i+1}[/imath]. The set of all [imath]E_{i,i+1}[/imath] partitions the boundary of the large polygon. Moreover, each [imath]E_{i,i+1}[/imath] must have length greater than or equal to the length of [imath]e_{i,i+1}[/imath]. The successive rays which isolate this from the rest of the boundary have some nonzero angle [imath]\theta[/imath] between them, and if they intersect the first polygon at length [imath]d_1[/imath] and the second polygon at length [imath]d_2>1[/imath], the length of [imath]e_{i,i+1}[/imath] is [imath]2d_1\sin(\theta)[/imath], and the length of [imath]E_{i,i+1}\geq 2d_2\sin(\theta)>2d_1\sin(\theta)[/imath]. So, each such subsection on the larger polygon has greater length than the corresponding subsection of the smaller polygon, so the sum of the larger polygon's subsections is greater than that sum of the smaller polygon. Since those subsections partitioned both polygons, each sum is the perimeter of the polygon, and so the perimeter of the larger polygon is greater than that of the smaller polygon.


To generalize to n-dimensions, do the same but with simplices from the interior point to each (n-1)-face of the interior polytope
EDIT: I see someone else wrote the same thing and there is a problem with it. My mistake

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 11:41 pm UTC
by stephentyrone
heyitsguay wrote:Moreover, each [imath]E_{i,i+1}[/imath] must have length greater than or equal to the length of [imath]e_{i,i+1}[/imath].


Antonfire gave a counterexample to this claim.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Tue Jul 27, 2010 11:45 pm UTC
by jestingrabbit
Fairly ugly answer.

Spoiler:
Firstly, I will assume that
  • a straight line is the unique shortest path between two points,
  • every line intersects the perimeter of a convex figure at most twice,
  • if you cut a convex polygon in two along a straight line you get two convex polygons,
  • the set that is the perimeter of a convex polygon uniquely determines that polygon and
  • given two distinct convex polygons, the perimeter of one cannot be contained in the perimeter of the other.

Assume A has n sides which are not subsets of the perimeter of B. I will construct a series of n+1 polygons, with each having less perimeter than the one before it, the first being B and the last being A. Let P0=B. To construct Pi+1 from Pi, first choose a side of A that is not a part of the perimeter of Pi, and extend that interval into a line, L. L will intersect the perimeter of Pi in two places, X and Y, and will not intersect the perimeter of A, save for the interval that it extends, by convexity. The perimeter of Pi+1 is then the interval from X to Y, union the part of the perimeter of Pi that is on the same side of L as A.

The perimeter of Pi+1 is shorter than the perimeter of Pi: we have taken a shortcut from X to Y. There is one fewer side of A which is not a part of the perimeter of Pi+1, so there are n-k sides of A which are not a part of the perimeter of Pk, and the perimeter of A is contained in the perimeter of Pn, so A=Pn.


Ugly, lots of assumptions, someone can do better.

Edit: foreshadowed by stephentyrone.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Wed Jul 28, 2010 7:50 am UTC
by skeptical scientist
jestingrabbit wrote:Fairly ugly answer.

Personally, I think it's quite nice. It's more or less the proof that I would have given. You do make a lot of assumptions, true, but your assumptions are all more basic than the result you are trying to prove, and some of them are practically axioms of geometry. It's not like every proof should start from the axioms - we generally accept that our readers know something, so we don't need to start from basic axioms every time we write a proof.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Wed Jul 28, 2010 8:29 am UTC
by jaap
I would prove it differently. Note that B, the outer polygon, need not be convex.
Spoiler:
On one side of A (the inner polygon) construct two perpendiculars, one at each endpoint.
The distance between these two parallel lines is the length of that side of A.
These two lines also intersect B, carving out a part of B's perimeter.
This part of B between the lines is at least as long as that side of A.
The above can be done on each side of A. As A is convex, the sides of A will carve out disjoint parts of the perimeter of B.
So the total perimeter of B is at larger than the perimeter of A.

In other words, I put semi-infinite strips on each side of A, and since B must cross all the strips, its perimeter must be at least the sum of the width of each of those strips, i.e. at least the perimeter of A.
B need not be convex, and may in fact be any closed curve containing A (and with a well-defined perimeter).

I'm not sure what all the assumptions are that I'm using. Jordan Curve Theorem certainly, although that is already implicit in the problem statement. Also that the shortest distance between two parallel lines is the length of a perpendicular between them.


You could even extend the above proof to show that if the distance between the two polygons is at least [imath]r[/imath], then the difference in perimeters is at least [imath]2 \pi r[/imath]. For this you would first need to show that any polygon surrounding a circle of radius [imath]r[/imath] has perimeter at least [imath]2 \pi r[/imath].

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Wed Jul 28, 2010 10:07 am UTC
by jestingrabbit
skeptical scientist wrote:Personally, I think it's quite nice.


Meh, to each their own. Its the sort of thing that an automated theorem prover might have come up with.


skeptical scientist wrote:It's not like every proof should start from the axioms - we generally accept that our readers know something, so we don't need to start from basic axioms every time we write a proof.


Agreed, and whilst the first is very nearly axiomatic, the second and third are consequences of convex sets being closed under intersections, and the fourth being fairly transparent, the fifth would need proof. The assumptions aren't really the problem though, it just has no finesse.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Wed Jul 28, 2010 3:27 pm UTC
by Yakk
antonfire wrote:
letterX wrote:How about: Pick a point C in the interior of the inner polygon. Draw rays from C to each of the vertices of the inner polygon. Because both the polygons are convex, and C is in the interior of both, each ray intersects each polygon exactly once.

Now, consider two adjacent rays, [imath]R_1, R_2[/imath] passing through the vertices [imath]v_1, v_2[/imath] of the inner polygon. Since they are adjacent rays, [imath](v_1, v_2)[/imath] is an edge of the inner polygon, and has length [imath]d(v_1, v_2)[/imath] (d is distance in the plane). Now, the rays [imath]R_1, R_2[/imath] intersect the outer polygon at points [imath]w_1, w_2[/imath] respectively (these points may not be vertices of the outer polygon, but we don't care). Since the outer polygon is outside the inner polygon, [imath]w_1[/imath] is further away from C than [imath]v_1[/imath], and similarly for [imath]w_2, v_2[/imath]. So, do some algebra and trigonometry to see that the straight line distance between [imath]w_1[/imath] and [imath]w_2[/imath] is at least [imath]d(v_1, v_2)[/imath].
This need not be true. Take C=0, v1=w1=(1,0), v2=(t,t2), w2=(1,t) for small t.

Visualizing this case might help:

We have our centre (0,0) from which we are drawing rays. The edge we are drawing rays from (v1, v2) is heading pretty close to strait towards the centre. The "outer" edge is relatively close to the inner edge, but orthogonal to a ray going out from the centre.

The extra distance away from the origin (which, in this case, can be small) that the outer edge has is dominated by the obliqueness of the inner edge. The inner edge, because it is nearly edge-on to our centre, casts a very small shadow on the outer perimeter when lit by a light from the centre.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Wed Jul 28, 2010 7:45 pm UTC
by FrancovS
I thought of a method which is quite similar to jestingrabbit's:
Spoiler:
Every convex polygon inside B can be obtained by removing triangles from B, assuming that these triangles have their vertices at one of the previous polygon's vertices and at the edges of the polygon which are connected to this vertex. Since each removal is a shortcut, the perimeter is smaller.

Proving that each one of these iterations result in a convex polygon is quite easy. Proving that you can obtain every convex polygon is a little more complicated, but is doable if you think the other way around: adding triangles to the smaller polygon until you get the big area. Get one face, create a triangle that reaches one edge, then fill the big polygon in a clockwise fashion.

I believe it can be extended to more dimensions if you remove tetrahedrons instead of triangles, and so on.

In retrospect, jaap's way seems a lot cooler.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Jul 29, 2010 1:14 am UTC
by aleph_one
These solutions are great! It's really nice to see multiple ways to solve the same problem. jestingrabbit's is reasonably clean and well-proved, much moreso than he/she gives it credit for. And I really like jaap's - now that I've seen it, I think of it as the reason that the statement is true. Also, both of these proofs can be extended into n dimensions.

@FrancovS: I'm not sure how this triangulation would work, and whether the perimeter would change the right way at each step. Could you spell it out?

My solution is somewhat like jaap's, but less nice, and more in the land of "how the hell do you think of that?" (answer: I saw the method used to solve a similar problem).
Spoiler:
Define the [imath]r[/imath]-expansion [imath]X_r[/imath] of a region [imath]X[/imath] to be the set of points within distance at most [imath]r[/imath] of some point in [imath]X[/imath]. If [imath]X[/imath] is a convex polygon, then [imath]X_r[/imath] consists disjointly (meaning without area overlap) of [imath]X[/imath], rectangles of height [imath]r[/imath] propped outward from the sides of [imath]X[/imath], and circular wedges of radius [imath]r[/imath] and total angle [imath]2 \pi[/imath]. Therefore,

Area[imath](X_r)[/imath] = Area[imath](X)[/imath] + [imath]r[/imath] Per[imath](X)[/imath] + [imath]\pi r^2[/imath]

Now, if [imath]A[/imath] and [imath]B[/imath] are convex polygonal regions with [imath]A \subset B[/imath], then for every [imath]r[/imath], [imath]A_r \subset B_r[/imath] and therefore Area[imath](A_r) \leq[/imath] Area[imath](B_r)[/imath]. So,

Area[imath](A)[/imath] + [imath]r[/imath] Per[imath](A)[/imath] + [imath]\pi r^2 \leq[/imath] Area[imath](B)[/imath] + [imath]r[/imath] Per[imath](B)[/imath] + [imath]\pi r^2[/imath].
Area[imath](A)[/imath] - Area[imath](B) \leq[/imath] [imath]r[/imath] [Per[imath](B)[/imath] - [imath][/imath] Per[imath](A)[/imath]] .

Since this holds for arbitrarily large [imath]r[/imath], we must have Per[imath](A)\leq[/imath] [imath][/imath] Per[imath](B)[/imath].
It's not clear to me how to extend this solution to higher dimension, or to arbitrary bounded convex areas. When I have a chance, I'll post another solution, given to me by a math professor to whom I posed this problem, that does extend in both these ways. I believe that it also suffices as a proof that every bounded convex region has a well-defined perimeter or surface area.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Jul 29, 2010 2:37 am UTC
by FrancovS
Well, to be honest, I'm not sure if this explanation is better than the original, but... the idea is to sculpt the inner polygon, but without affecting the convexity of the initial shape. To do so, you are only allowed to do cuts that can be achieved by folding paper, which is, trace a line that divides the polygon and discard one of the sides. The cut made is a shortcut, so the new perimeter is smaller. To simplify the problem, I will assume that only cuts that result in removing one triangle are allowed. Now I will show that, using only these triangle removal steps, you can obtain any convex polygon from inside another polygon. Doing so is easy if you think of the process backwards: start with the small polygon. Then start adding triangles to the edges, but without affecting it's convexity. You can reach one of the edges of the outer polygon, and start filling it up with triangles in a circle.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Jul 29, 2010 4:05 am UTC
by Torn Apart By Dingos
I really like this puzzle and I look forward to seeing the second solution from you, aleph_one. :) Post more puzzles!

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Jul 29, 2010 9:57 pm UTC
by aleph_one
Here's a solution given to me by a math professor:
Spoiler:
The result follows easily from the following theorem, which we will prove.
Theorem wrote: The perimeter of a convex planar polygon equals [imath]\pi[/imath] times the average length of its orthogonal projections over all directions.

In other words, imagine putting the Sun infinitely far away in some direction, and finding the length of the line segment that is the polygon's shadow falling onto a line perpendicular to the sun's rays. The polygon's perimeter is proportional to the length of this shadow averaged over all directions that the Sun could in, which correspond to angles from 0 to [imath]2 \pi[/imath]. (I've forgotten the name of this result, it's called some famous guy's theorem; I'd be obliged to anyone who can find a reference. Also, I think this result, if extended to convex, bounded planar regions, implies that every such region has a well-defined and finite perimeter.)

This theorem implies the result, since if A lies inside B, then every shadow of A lies within the corresponding shadow of B, and so the average shadow size of A is at most that average shadow size of B, and therefore the perimeter of A is at most that of B.

Now we'll prove the theorem. I'll try to use words rather than symbols so as to be non-technical.

First, we note that if we orthogonally project a line segment in the plane along a fixed direction (i.e. take its shadow from an infinitely far light source onto a line perpendicular to the light rays), the shadow's length scales with the segment's length. So, the average length of a projection in a random direction is proportional to the segment's length. We could find the constant of proportionality by integrating over all angles, but instead will defer finding it until later using a trick.

Now, the perimeter of a polygon is made of line segments. By linearity of expectation, the average total length (over all projection directions) of the shadows of the polygon's side (taken separately) equals the sum of the each side's average shadow-length, which is proportional to the length of the side. Therefore, the average total shadow length of the sides is proportional to the sum of their lengths, which is the polygon's perimeter.

Next, we note that the shadow of the polygonal region is covered by the shadows of its sides. In fact, since each ray from the Sun passes through the polygon twice, the shadows of the sides doubly cover the shadow of the polygon. So, the length of the shadow of the polygon is half the length of the shadows of the sides. Averaging over the shadows gotten from all directions, we find that the average length of the shadow of the polygon is proportional to the polygon's perimeter.

We can find the constant of proportionality by a single example. We see that the results should hold for a circle if we approximate it by regular polygons. A circle of radius 1 has circumference [imath]2 \pi[/imath], and expected shadow size of 2 (since every shadow has the length 2), giving us the proportionality constant [imath]\pi[/imath].

This proof extends to any number of dimensions. So, the surface area of a 3D polyhedron is proportional to the average area of its shadow in a random direction onto a perpendicular plane, and the constant of proportionality can be found by considering the sphere (it's 4). Here, the average is taken over projection directions corresponding to the vectors on the unit sphere.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Mon Aug 02, 2010 12:44 am UTC
by silverhammermba
I haven't formally thought through this, but my intuition is that since both polygons are convex, we should be able to construct a circle C with the same area as A and a circle D with the same perimeter as B such that C is nested inside D. The claim would follow since A's perimeter would be less than or equal to C's which is trivially less than D's which is equal to B's.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Mon Aug 02, 2010 4:09 pm UTC
by WarDaft
silverhammermba wrote:I haven't formally thought through this, but my intuition is that since both polygons are convex, we should be able to construct a circle C with the same area as A and a circle D with the same perimeter as B such that C is nested inside D. The claim would follow since A's perimeter would be less than or equal to C's which is trivially less than D's which is equal to B's.

That doesn't strictly follow.

Consider two long thin rectangles. The one formed from the perimeter could be quite large, while the one formed from the area could be quite small.

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Aug 05, 2010 2:04 pm UTC
by skass
The theorem mentioned by aleph_one is attributed to Cauchy, sometimes as his "Surface Area Formula." Here are a couple of references: http://www.springerlink.com/content/j223806806552288/, http://www.jstor.org/pss/2034228

Re: Polygon inside a polygon: A surprisingly tricky problem

Posted: Thu Aug 05, 2010 5:33 pm UTC
by aleph_one
Thanks for the references, skass!