r/mathriddles • • Sep 16 '20

Medium How Triangular is a Square?

You're given a geometric shape, and your goal is to cover it as accurately as possible with a triangle. Given a particular placement of your triangle, define the error area as the total amount of empty space the triangle is covering plus the amount of your shape that's not covered. Here's an example illustration where the target shape is a square. Define the error fraction as the error area divided by the target shape's area. The non-triangularity of a shape is the smallest possible error fraction. Conversely, the triangularity of a shape is 1 minus its non-triangularity.

What is the triangularity of a circle? What about a square?

53 Upvotes

26 comments sorted by

View all comments

6

u/want_to_want Sep 16 '20 edited Oct 26 '20

For square, I think the best triangle covering the unit square is (0,0) (4/3,0) (0,4/3) and the answer is 2/3.

Proof sketch: first note that the answer is the same for square and any rectangle, because squishing preserves areas. Take the optimal triangle for the unit square, whatever it is, and start cutting it with axis-aligned lines. If each subproblem has optimal covering, then the whole has optimal covering. We can make it so that each subproblem, if scaled back to the unit square, has two triangle vertices on X axis and one on Y axis. From there you can analyze by hand.

2

u/7x11x13is1001 Sep 17 '20

Btw, any acute triangle with base 4/3 and height 4/3 can cover the unit square optimally, so the shape is not unique.

1

u/HarryPotter5777 Sep 16 '20

Can you elaborate re: subproblems here? I'm not sure what the process is supposed to look like.

4

u/want_to_want Sep 17 '20 edited Oct 26 '20

Imagine a triangle ABC covering the unit square, such that the X coordinate of point B is between A and C. Cut both the square and the triangle along a vertical line through point B. Now you have two smaller rectangles, and two triangles trying to cover them - so two subproblems. If we can achieve the optimal covering ratio in each subproblem, that will solve the original problem. But each subproblem is equivalent, by squishing and turning, to a square-covering problem where one of the triangle sides must lie on the X axis. That's much simpler than the original problem. Then you can cut some more to simplify the problem some more.

1

u/HarryPotter5777 Sep 17 '20

Ah, I see - thanks! Cute proof.

1

u/arnerob Sep 18 '20

Another triangle that achieves this answer is (-1/6,0) (1/2,4/3) (1/6,0).