6
$\begingroup$

This question is somewhat dual to my previously stated question about Maximum area of the intersection of a parallelogram and a triangle, where the triangle and parallelogram each is assumed to be of unit area.

Now I ask:

Question. Suppose a parallelogram is of area 1 (say, the unit square if you prefer) and a triangle is of area $1$ as well, then what is the minimum area of the convex hull of the union of the parallelogram and the triangle?

It is obvious that the minimum exists and is greater than $1$. The best I can do is $\sqrt{2}$ $-$ is this the minimum?

My example is: the unit square and the right triangle with legs of length $\sqrt2$ each, the triangle's right angle coinciding with the square's corner. (Added by Joe's request.)

In fact, there is a continuous cyclic family of examples, each producing the same area of the convex hull:

Figure 1

An analogous question can be asked in three dimensions, replacing parallelogram with parallelepiped (or cube, if you prefer) and triangle with simplex or pyramid with a parallelogram base, each of unit volume.

$\endgroup$
  • 1
    $\begingroup$ are the triangle and parallelogram variables in the question, or given? $\endgroup$ – Yaakov Baruch Apr 10 at 11:14
  • 1
    $\begingroup$ Could you describe your $\sqrt{2}$ example? $\endgroup$ – Joseph O'Rourke Apr 10 at 11:56
  • 2
    $\begingroup$ @JosephO'Rourke: done. $\endgroup$ – Wlodek Kuperberg Apr 10 at 16:05
  • 1
    $\begingroup$ One way I see to make this more tractable is to show that, if the unit square is $\{\pm\frac12, \pm\frac12\}$, then up to rotations there must be one triangle corner each with $x\le-\frac12, y\ge-\frac12;$ and with $x\ge-\frac12,y\ge\frac12;$ and with $x\ge\frac12, y\le\frac12$. $\endgroup$ – Matt F. Apr 11 at 16:32
  • 1
    $\begingroup$ A $\sqrt{2}$ example is also achieved by a unit a square and an isosceles triangle of base and height $\sqrt{2}$, with the base centered on that of the square. $\endgroup$ – Yaakov Baruch Apr 11 at 20:43
2
$\begingroup$

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 algebraic 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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