9
$\begingroup$

I try to find the smallest parallelogram in terms of area that contains a convex quadrilateral(A,B,C,D).

I am pretty sure it must be constructed from two neighboring sides of the quadrilateral.

But which ones?

I have no approach for a condition like "smallest angle" or "shortest distance" ect.

$\endgroup$
4
  • 1
    $\begingroup$ What is meant by "smallest parallelogram"? The one with least area? The one with least diameter (as a set)? The one with least perimeter? $\endgroup$
    – mniip
    Commented Feb 22, 2017 at 3:34
  • $\begingroup$ area, thanks for pointing that out $\endgroup$
    – Dromlius
    Commented Feb 22, 2017 at 3:38
  • 2
    $\begingroup$ It seems someone has already worked this out here. $\endgroup$
    – Jens
    Commented Feb 22, 2017 at 5:41
  • $\begingroup$ @Jens thank you! But if I understand the paper correctly it "just" tries different parallelograms and is efficient for polygons with 5 or more vertexes. I hope there is a simpler solution for my case with only convex quadrilateral. $\endgroup$
    – Dromlius
    Commented Feb 22, 2017 at 15:37

1 Answer 1

1
$\begingroup$

The paper cited by @Jens proves that you are correct in your belief about using two neighboring sides. That's much better than "pretty sure."

Regarding which ones, if your convex quadrilateral is itself a parallelogram, then clearly it is its own minimum enclosing parallelogram (MEP). Otherwise the MEP is not unique, because in all other cases at least one side of any MEP is longer than it "needs" to be, and you can "slide" it along the line on which it lies to obtain another MEP.

if two sides of the convex quadrilateral are parallel, then both of them lie on any MEP, since at least one does. Consider the longer parallel side: the side of the MEP on which it lies must be at least as long. The area of the MEP is therefore at least the product of the longer parallel side of the original quadrilateral and the distance between the parallel sides. You can construct an MEP with exactly that area by taking the longer parallel side as one side of the MEP and either adjacent side as another side of the MEP.

If no sides are parallel, find a side $AB$ whose two vertices have interior angles whose sum is less than $180$ degrees. One of the two adjacent sides, say $BC,$ must lie on an MEP, and a brief inspection confirms that there is an MEP with one side equal to $AB$ and the other containing $BC.$

Therefore a side whose interior angles sum to less than $180$ degrees may be used as one edge of an MEP. One of the adjacent sides will also have interior angles whose is less than $180$ degrees; it is the other side of an MEP.


Short version: find three vertices of the convex quadrilateral such that the sum of interior angles of either adjacent pair of vertices is no greater than $180$ degrees. Those three vertices are vertices of an MEP.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .