Find the minimum area parallelogram enclosing all triangles

0
votes

Following is the problem statement.

  1. You have been given k number of equilateral triangles (There is a upper cap on k, lets say k=<15). The triangles can be overlapping.

  2. Now you have to find a parallelogram enclosing all the triangles and has the minimum area. It is given that two opposite edges of the four edges are parallel to either X axis or Y axis(That is your choice).

My Approach:

Let's say two of them are parallel to Y axis.

Then the leftmost point and the rightmost point of the set of triangles will lie in two opposite edges of the parallelogram. Now I will draw two straight lines which pass through these points and are parallel to the Y axis.

This way I have found two edges its not so difficult. Now I am stuck and don't know how to find other two. I thought a lot but since I was unable to make it out I am posting it here. Any help will be appreciated!!!!!!!

1
javapythonalgorithmdata-structurescomputational-geometry
Please post your code. Words alone are not really enough to understand what's going on here. – Malphrush
Draw it on paper to visualize the steps, then translate those steps to code. Try several different examples on paper. Post your code if you run into issues. – Andrew S
With the problem as stated there doesn't seem to be any way to exploit the fact that the points lie at the vertices of equilateral triangles. Is it possible there's another constraint that's been missed? – RaffleBuffle
no constraint has been missed. – NIght King

1 Answers

2
votes

Build convex hull around all triangles vertices.

Then use rotating calipers to get a pair of parallel lines with the smallest vertical distance between them (parallelogram area is defined by height (here horizontal) - it is already fixed, and by vertical base length - choose minimum)