I am interested specifically in the intersection of triangles but I think this is true of all convex polygons am I correct? Also is the largest possible inscribed triangle of a convex polygon always composed of at least two of the polygons vertices? (At first I thought it was 3 vertices but then I thought of a square and realized that the max inscribed triangle was any two connected vertices and any point on the adjacent side.) I am interested in finding the maximum inscribed triangle of the intersection of several triangles is in the below image. If you are interested in the context of the question please see this question: How to find the intersection of the area of multiple triangles
Is the area of intersection of convex polygons always convex?
-
7The arbitrary intersection of any convex sets is convex. – 2012-12-31
-
0@MichaelGreinecker Any ideas regarding the inscribed triangle question? – 2012-12-31
2 Answers
Sigur and Michael already responded to the part of your question regarding the intersections of convex sets being convex so I'm going to skip that.
The second part of your question is then about inscribing triangles in convex polygons. If you're looking to maximize area, then all three vertices of the triangle can be assumed to be vertices of your polygon. In other words: there exists a triangle maximizing area whose vertices are all polygon vertices.
Why? The method below is certainly not the most direct method to do it, but I like arguments of this sort because they give you intuition about the structure of the problem. I am not being 100% rigorous but pretty close to it, you can fill in the details pretty easily.
Suppose your convex polygon is $P_1 P_2 \cdots P_n$ and $\triangle ABC$ is a triangle with maximal area. (At least one such exists, in view of $P_1 P_2 \cdots P_n$ being compact.) Clearly $A$, $B$, $C$ must all lie on the boundary of the polygon otherwise you can stretch them out and increase the area.
Now suppose that any one of $A$, $B$, $C$ is not a vertex of our polygon. Without loss of generality, then, we may suppose that $A$ lies inbetween $P_1$, $P_2$. (Draw a diagram, it will help.)
For starters, note that this forces $BC$ to be parallel to $P_1 P_2$. Indeed if it weren't, then the triangle height from $A$ onto $BC$ would increase monotonically if we were to translate $A$ towards either $P_1$ or $P_2$ (and decrease monotonically in the other direction). This contradicts the maximality of the area of $\triangle ABC$, because perturbing $A$ slightly would result in an inscribed triangle with larger area (same base, bigger height). Note that the perturbed triangle is stil inscribed in view of the polygon's assumed convexity (check this). Therefore $BC$ is parallel to $P_1 P_2$.
In this case we may gradually translate $A$ to coincide with your favorite point among the pair $P_1$, $P_2$ without altering the area of the triangle, since we're keeping the same base and the height does not change in view of $BC$ being parallel to $P_1 P_2$. Translating $A$ does not affect the triangle being inscribed since our polygon is convex (like above).
What have we achieved? Well, start with some arbitrary maximal triangle and one by one translate its vertices along the boundary edges in such a way to preserve area, until the vertex coincides with a polygon vertex. Do this for all triangle vertices. End up with a maximal triangle whose vertices are polygon vertices. Done.
EDIT: Since we have come this far, we might as well describe an algorithm to actually find a triangle with maximal inscribed area. The method described above is not intended for that purpose since it's only good for finding local maxima (something that Rahul has also pointed out), but it does hint towards a more general approach.
Of course since we've shown that we can take maximal triangles to have polygon vertices, there is a silly $\Theta(n^3)$ algorithm that iterates over all possible such triangles and finds the one of maximal area. But we can do better: as Sigur pointed out we can maximize over all pairs $(L, h_L)$ where $L$ is a line connecting a pair of vertices and $h_L$ is an optimal height onto this line. You can do this by iterating over all $n^2$ pairs of vertices (to determine $L$) and then using binary search to determine the optimal $h_L$ in view of convexity, for a total runtime of $\Theta(n^2 \log n)$. You can actually kill the $\log n$ factor by using a careful amortization technique when iterating over the second vertex in $L$, solving the problem in $\Theta(n^2)$. My algorithm skills are not what they used to be, maybe there's an even faster way to do it. I'd be very happy to hear it.
-
0+1, this implies that there is a global maximum attained by a triangle with its vertices coinciding with polygon vertices. However, it is worth mentioning that the method here only gives a locally maximal triangle, which may not be the global maximum (e.g. consider a hexagon obtained by taking an equilateral triangle and moving its edge midpoints slightly outward). – 2013-01-03
-
0Hi Rahul, I'm afraid I don't understand the point you're making. EDIT: To be clear, as you pointed out, this was not supposed to be a constructive method for global maxima (i.e. start with a triangle, wiggle it around, construct a global maximum). All it does is start with a triangle and make a triangle that is at least as good, and whose vertices are nice. So bootstrap it with a maximal triangle and voila. – 2013-01-03
-
0Now it's my turn to not understand your last sentence. – 2013-01-03
-
0This isn't getting us anywhere :-) If perhaps you think my original presentation is not clear, I will be happy to throw in more details to straighten it out. – 2013-01-03
-
0No, no, your presentation is perfectly fine. I just wanted to mention the local vs. global maximum issue as I felt a naïve reader might miss that point. – 2013-01-03
-
0+1 (+2 if it would be possible). Nice description, only using basic geometry. Great! Now we can think how to determine the maximal triangle. We should to write all the pairs $(L,h_L)$ where $L$ is the length of a side and $H_L$ is the possible heights wrt the side $L$. Then we choose the maximal pair. – 2013-01-03
-
0Thanks Sigur! _Now_ I see what was going on with Rahul, I guess the OP also wanted a way to _determine_ what the maximal triangle is. My apologies for missing that. You're right Sigur, I think maximizing among all pairs $(L, h_L)$ is the best way to do it, let me edit my post above to reflect your point. – 2013-01-03
-
0@Christos Thanks! I also enjoy arguments of that sort. I am a software engineer and not a mathematician so often the “most direct" route is so incomprehensible to me that I never reach the destination. I was able to follow your argument and gain some insight into the problem. Thanks for taking the time to help me! – 2013-01-07
-
0You are welcome my friend. – 2013-01-07
Let $C_i$ convex sets. For any points $a_i,b_i\in C_i$ the segment $a_ib_i$ is contained on $C_i$. So if $p,q\in C_1\cap C_2$ then the segment $pq$ is contained on $C_1\cap C_2$ also. So the intersection is again a convex set.