r/mathriddles • u/BruhcamoleNibberDick • 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?
4
u/VitulusAureus Sep 16 '20
Also: What is the least triangular shape? Or: how to construct a shape with a very low triangularity?
6
u/BruhcamoleNibberDick Sep 16 '20
That's an interesting question. I think you'd have to restrict it to convex shapes or something similar to get an answer that's not "arbitrarily small". Even with the restriction of closedness, a shape like this could be made arbitrarily non-triangular. This shape has small "islands" of area connected by arbitrarily narrow "channels" of insignificant area. I think you can make the triangularity arbitrarily low by increasing the number of islands and the distance between them.
1
u/buwlerman Sep 18 '20
Three observations about the edges of a triangle that minimize the error fraction when dealing with a convex set. Consider edges that intersect with the boundary of our set exactly two times. These two intersections split the edge in three parts. Call these a, b and c. a and c are outside the convex set, and b is inside. Extending or shortening the triangle along our edge by a small amount has the effect of changing the error fraction by a multiple of a -b +c (in the limit). The sign depends on if we're extending or shortening. Since the triangle minimizes the error fraction this can never be negative, so it must be zero and b = a + c.
If we instead only extend on one side of our edge, say the part closest to c and keep the vertex by a fixed, we (in the limit) change the error fraction by a multiple of a2-2ab-b2+2ac+2bc+c2, which again has to be zero. By symmetry we can also exchange a and c, and subtracting the resulting equation from the first and doing some algebra yields c=a. From the last paragraph we also get b = 2a.
Until now we have dealt with edges with exactly two intersections. If they intersect less than two times, then it is trivial that the triangle is not optimal. If they intersect more than two times, then it coincides with a boundary line of our set.
This can be used to find the triangularity of the circle, but things get difficult for shapes with line segments as part of their boundary. Maybe someone can show that the shape with least triangularity must have a curved boundary?
1
u/BruhcamoleNibberDick Sep 18 '20
Those are some very useful properties. I haven't checked the algebra on your second point, but i'll take your word for it for now. Considering your last point, it could be an interesting problem on its own to find the least triangular convex set with a curved boundary.
3
u/PeteOK Sep 16 '20 edited Sep 16 '20
Your post prompted me to ask about this on Math Stack Exchange: https://math.stackexchange.com/q/3829029/121988
3
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
1
1
u/TreeHandThingy Sep 16 '20 edited Sep 16 '20
Are there parameters for the triangle? Is there some positional/size restrictions for this? Or are you asking for an optimized situation?
EDIT: I misread the question. I must've skimmed over the "smallest possible error" bit.
6
u/BruhcamoleNibberDick Sep 16 '20
No, there are no restrictions on the triangle in terms or size, orientation, or being equilateral/isoceles etc. Essentially, all six of the triangle's vertex coordinates are free.
-6
u/TreeHandThingy Sep 16 '20 edited Sep 16 '20
Then I can't help but feel the problem isn't well-defined. I could take a tiny triangle and place it anywhere, and have wildly varying answers that don't lead to any sort of useful conclusion. The "answer" to this riddle is likely some complicated, but predictable, formula that can be derived by placing the shapes on a cartesian plane.
EDIT: I can't read.
7
u/BruhcamoleNibberDick Sep 16 '20
Placing a small triangle somewhere will get you a very large (i.e. close to 1) error fraction, because most of the shape isn't covered. The number you're looking for is (one minus) the smallest possible error fraction.
1
u/TreeHandThingy Sep 16 '20
Okay, I misread the question. I must've just skimmed over the "smallest possible error" part. Carry on.
5
2
u/Bitter_Illustrator_6 Sep 17 '20
To solve it for the circle:
Start with the following lemma. Consider two points A and B on a circle centred at O. Suppose that a chord intersecting the circle twice on the minor arc AB has (perpendicular) distance z from O, and intersects the lines AO and BO at P and Q respectively. Consider the shapes S1. the triangle PQO and S2. the sector bordered by AO, BO and the minor arc AB, and the 'symmetric difference' of these shapes: that is, the area of the combined regions in one shape but not the other (red region in the original figure posted). Then amongst all ABO with a given z, this symmetric difference is minimised when AQ=BQ.
This is straightforward to prove: suppose the minor arc subtends angle θ, and the perpendicular from O to PQ is at angle φ from OP. Then the area of OPQ is (1/2) z^2 (tan(φ) + tan(θ-φ)); the area of the minor segment of the chord is constant, and the area of the two sectors of the circle enclosed by ABO is constant, so the area of OPQ is monotonic to the symmetric difference. The area of OPQ is minimised when φ=θ/2, as required.
Now suppose we have some general triangle ABC covering a circle Γ with centre O. Hopefully it's clear that the triangle which minimises the error area will have all three vertices outside Γ. So we have three lines AB, AC, BC, each of which intersect the circle twice. By the lemma, we can replace each of these lines by a new line such that the resulting figure (while not a triangle) will have a lower error area than the original triangle. The new line for AB will intersect OA and OB at P and Q such that OP=PQ, etc.
We now don't have a triangle; we have three separate isosceles triangles with apices at the centre of the circle. Supposing the circle has radius 1 and such an isosceles triangle has variable height h and apical angle A, the error area of the isosceles triangle is minimised when h=2/√(4+ tan(A/2)^2). So if we replace each isosceles triangle with apical angles A1, A2, A3 with isosceles triangles with the optimum height, then our figure (still not a triangle) has lower error area.
But this function f(A)=2/√(4+ tan(A/2)^2) has negative second derivative on (0,pi). The three isosceles triangles have apical angles A1, A2, A3, summing to 2π - so we can apply Jensen's inequality to guarantee that f(A1) + f(A2) + f(A3) ≥ 3 f( (A1 + A2 + A3)/3 = 3f(2π/3). So we can replace each of the angles A1, A2, A3 with 2π/3 to get a lower error area - and now we have a triangle! (the equilateral triangle). So the triangle with minimal error area for Γ is, indeed, equilateral and centred at O. The actual error area is 6 acos(2/Sqrt(7)))/π - 1.
TLDR: Basic idea is replace an arbitrary triangle with three isosceles triangles each with apex at the circle centre, change the heights of these triangles, then change the apical angles, with each step decreasing the error area and eventually ending with an equilateral triangle.
Square is harder, will try tomorrow.
I'm sorry not to have diagrams, maybe someone else can fill them in
9
u/pichutarius Sep 16 '20
for circle, assume the answer is an equilateral, whose center coincides with center of circle.
then the triangularity = 6/pi*arctan(sqrt(3)/5) = 0.363113
its just basic but annoying geometry+calculus calculation.
if equilateral is not the answer, then pick a vertex of triangle A, construct line passing through center of circle and A, which divides the problem into 2 halves, if one halve is better than the other, just replace the worse half with the better half. repeat many times, the limit is an equilateral.
it is not a rigorous proof but i just cant conceive the contrary. i do welcome others to either provide a rigorous proof or a counter example to drop my jaw.