Skip to main content
2 of 3
clarified which formula is remarkable
user avatar
user avatar

This isn't a full answer, just an algebraic simplification.

enter image description here

Let a square have vertices $(\pm \frac12, \pm \frac12)$. Suppose a triangle has vertices $(a,b),(c,d),(e,f)$ satisfying:

$$c \le -1/2 \le e \le 1/2 \le a$$ $$f \le -1/2 \le d \le 1/2 \le b$$

Then the convex hull of the square and triangle has area

$$\phantom{+}\max(a-c+b-d,\ 2ad-2bc)\,/\,4\\+\max(a-e+b-f,\ 2be-2af)\,/\,4\\+\max(e-c+d-f,\ 2cf-2de)\,/\,4$$

This surprisingly simple formula is the result of summing the area of the square, the four white triangles bordering it, and any positive areas for the gray triangles.

For instance, the contribution of the triangle on $(a,b),(c,d),(-1/2,1/2)$ is $$\max(0,\left| \begin{align} a\ \ \ \ &\ \ \ \ b &\!1\\ c\ \ \ \ &\ \ \ \ d &\!1\\ -1/2\ \ &\ \ 1/2 &\!1 \end{align} \right|/2)$$ If the triangle has a positive signed area, then the line between $(a,b)$ and $(c,d)$ is above the corner of the square, and the triangle area should be included in the convex hull.

If the triangle has a negative signed area, then the line is below the corner, and the triangle area should not be included in the convex hull.

I'd welcome an explanation for the overall area formula that doesn't go through a bunch of determinants and algebriac simplification. In any case, the formula is simple enough that we can reasonably ask a computer algebra system to minimize it subject to the inequalities and the area constraint on the triangle.

Furthermore, I think these inequalities hold generically for all minimizing answers to the original problem. If the triangle has vertices $(a,b),(c,d),(e,f)$, then one of them is highest, one of them is lowest, one of them is leftmost and one of them is rightmost. By the pigeonhole principle, two of those designations must coincide. So we can assume without loss of generality that $(a,b)$ is highest and rightmost, $(c,d)$ is leftmost and $(e,f)$ is lowest. Thus at a minimum we have $$c \le e \le a$$ $$f \le d \le b$$ and I think the other inequalities follow too.

user44143