• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Sum of sides of n polygons in quadrilateral is no more than 4n

1,456
44
Problem Statement
Say that we have a convex quadrilateral, and then draw a finite number of lines inside of it. Then, it's clear that the quadrilateral is now made up of a finite number of, say, ##n## polygons. Let ##s_i## be the number of sides of polygon ##n##. Is it possible that ##\sum s_i > 4n##?
Relevant Equations
N/A
I can construct examples that are less than or equal to ##4n## quite easily, but for the life of me I cannot come with example where it's greater than
 

fresh_42

Mentor
Insights Author
2018 Award
10,039
6,780
Problem Statement: Say that we have a convex quadrilateral, and then draw a finite number of lines inside of it. Then, it's clear that the quadrilateral is now made up of a finite number of, say, ##n## polygons. Let ##s_i## be the number of sides of polygon ##n##. Is it possible that ##\sum s_i > 4n##?
Relevant Equations: N/A

I can construct examples that are less than or equal to ##4n## quite easily, but for the life of me I cannot come with example where it's greater than
So why don't you try and prove that it is impossible? Also: do the lines have to cut the quadrilateral? And how? Otherwise I could simply draw an 5n polygon inside of it, or with one side being part of a side of the quadrilateral. And has it to be convex?
 
1,456
44
A line in this case is a segment from one side of the quadrilateral to the other.

Here is the problem I am actually trying to solve: Let ##Q## be a convex quadrilateral which is cut into convex pieces (cells) by a finite number of lines. For any collection ##(Q_i)_1^n## of these cells, decompose ##Q## into nonoverlapping convex polygons ##(R_i)_1^n## so that ##Q_i \subset R_i## for every ##i##, and ##\sum s_i \le 4n##, where ##s_i## denotes the number of sides of ##R_i##.

Here is my question: When I draw some lines the resulting ##(Q_i)_1^n## always seem to satisfy that ##\sum s_i \le 4n##, so why do we need the ##(R_i)_1^n## at all?
 

fresh_42

Mentor
Insights Author
2018 Award
10,039
6,780
I see the need to rule out overlapping to avoid a multiple count, and to remain convexity. It also rules out, that a cell is considered as a part of two polygons. So I'd say it's a technical statement to rule out double counts.
 

andrewkirk

Science Advisor
Homework Helper
Insights Author
Gold Member
3,715
1,344
When I draw some lines the resulting ##(Q_i)_1^n## always seem to satisfy that ##\sum s_i \le 4n##, so why do we need the ##(R_i)_1^n## at all?
The set of partitions of the quadrilateral into the ##Q_j## is a proper subset of the set of all partitions into ##R_j##. Consider the partition of the square with diagonally opposite corners at (0,0) and (2,2) into the following three convex polygons:
  1. ##R_1##: triangle with vertices (0,0), (2,0), (1,1)
  2. ##R_2##: quadrilateral with vertices (0,0), (0,2), (1, 2), (1,1)
  3. ##R_3##: quadrilateral with vertices (2,0), (2,2), (1, 2), (1,1)
That partition cannot be made by a set of lines cutting the square, without combining elements. We can partition the square into six triangles by cutting with the lines ##y=x,\ x=1,\ y+x=2##, but we need to combine pairs to get the partition above.

So proving the result for the ##R_j## partitions is a stronger theorem than proving it for only the ##Q_j## partitions.

However, it should not be hard to show that every R partition can be formed by amalgamating elements of a Q partition, and that amalgamating always reduces the edge sum. So once those two are proved, plus the lemma of the next paragraph, the problem can be reduced to proving that the result holds for all S partitions.

I note that the problem contains a hidden supposition: that for every Q partition there exists at least one R partition such that every R cell contains exactly one Q cell. That that can be done is not immediately obvious, so a lemma is needed to show that this can be done. It is easy to see that the quad can be partitioned into n polygons, each containng exactly one Q cell, but not necessarily that it can be done so that each of those polygons is convex.

EDIT: It turns out to be easy to prove the problem stated in the OP. Not so easy to prove the problem stated in post #3. I do not yet have a proof of that harder problem. Note also that a full statement of the harder problem says that, for every Q partition by straight lines and list of n Q-cells, there exists a partition of Q into convex polygons (R-cells), formed by amalgamating cells in the Q partition, such that each R-cell contains exactly one of ##Q_1,...,Q_n## and the edge total from that R partition does not exceed four times the partition size.

It does not say that every partition into convex polygons such that each R-cell contains exactly one of ##Q_1,...,Q_n## satisfies the four-times relationship. We can construct a counterexample to that by tesselating the square with hexagons and cutting each corner of the square with a little snip line near the corner, so that every R cell contains exactly one Q cell.
 
Last edited:

Want to reply to this thread?

"Sum of sides of n polygons in quadrilateral is no more than 4n" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top