Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

share|improve this question
5  
The arbitrary intersection of any convex sets is convex. –  Michael Greinecker Dec 31 '12 at 16:45
    
@MichaelGreinecker Any ideas regarding the inscribed triangle question? –  vanattab Dec 31 '12 at 17:23

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
+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). –  Rahul Jan 3 '13 at 4:51
    
Hi 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. –  Christos Jan 3 '13 at 5:25
    
Now it's my turn to not understand your last sentence. –  Rahul Jan 3 '13 at 5:42
    
This 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. –  Christos Jan 3 '13 at 5:56
    
No, 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. –  Rahul Jan 3 '13 at 6:40

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.