6

You are given a triangle and a segment on a plane. The segment is longer than any of the triangle's sides. How can you translate and/or rotate the triangle or the segment such that the resulting convex hull has minimal area and the segment doesn't cut the triangle?

The segment has to be tangent to the triangle otherwise moving it towards the triangle until it collides with it will reduce the area of the convex hull.

I thought it would be pretty simple to prove that the segment would have to overlap one of the triangle's sides but failed so far. Could you help me to prove or disprove this?

Example with segment and triangle disjoint

Example with triangle and segment overlapping

Marc Grec
  • 667

1 Answers1

5

Your second paragraph shows that one side of the triangle must be part of the (moved) line segment.

If it touches at just a vertex you can rotate it to reduce the distance to both the other vertices of the triangle. That will reduce the area of the convex hull.

Then the minimum area of the convex hull will occur when the longest side of the triangle lies on the segment, and it does not matter where on that segment the side lies.

To see why, note that the convex hull is a triangle with third vertex the other vertex of the triangle. These all have the same altitude, so the same area. The area will be smallest for the side with the smallest altitude. That's the longest side.

So the area of a minimal convex hull is half the product of the length of the segment and the shortest altitude of the triangle.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • I agree with what you said and I hope that is the true answer but how can you prove that the line overlaps with the triangle and it doesn't just go through a vertex of the triangle? – Marc Grec Sep 05 '21 at 16:36
  • @MarcGrec See my edit. – Ethan Bolker Sep 05 '21 at 16:40
  • 1
    Rotating the line segment around a vertex will not necessarily reduce the distance to both other vertices -- in particular that is not the case when the segment is parallel to the opposite side. – Troposphere Sep 05 '21 at 20:31
  • @Troposphere Fair point. But in that case just translating the segment across the triangle to the parallel side reduces the figure from a trapezoid to a triangle of smaller area. – Ethan Bolker Sep 06 '21 at 01:08
  • 1
    Sure, in that easy-to-describe case. And I'm not seriously doubting the conclusion; I just don't find the argument presented so far convincing. It's not obvious to me that there's always either an infinitesimal rotation of the triangle or a translation to the other side that will decrease the area. (In the rotation case it's also possible that both the other corners will decrease in altitude, but the area of the enclosing quadrilateral nevertheless stays constant (to first order) because the rotation increases the lateral distance between those corners). – Troposphere Sep 06 '21 at 03:57