0
$\begingroup$

I am toying around with a shape problem and I am looking for a more clever solution than what I have been able to come up with.

Here is the problem:

I have a set of points that form an enclosed shape on a Cartesian grid, say $A(-1, 0)$, $B(1, 0)$ and $C(0, 4)$ which forms an acute triangle.

The problem I am trying to solve is I need to be able to rotate a well formed shape in such a way that the maximum distance between points on the periphery is as small as it can be. This point is essentially to find a rotation where the shape has the least width possible on the x-axis. The example above would have an answer that is the distance between A and B(I think?)

I can come up with very naive solutions to this for common shapes like rectangles and what have you, but it seems like there must be a universal way to solve this problem that will work for any shape.

Any nudge in the right direction would be greatly appreciated.

  • 0
    @nsfyn55 Unless we are miscommunicating, I disagree. The following three vertices are a rotated version of your triangle. You can check pairwise distance if you like. It has been translated to make some coordinates nice rational numbers. $A(0,0)$, $B(\frac{8}{\sqrt{17}},\frac{2}{\sqrt{17}})$, and $C(0,\sqrt{17})$. This triangle has its minimal x-width as $\frac{8}{\sqrt{17}}\approx1.94<2$. And the method here (rotating to make the longest side vertical) will apply to any triangle.2012-03-15

1 Answers 1

2

If we can rotate by any angle:

  1. Calculate the convex hull of the points and sort them counterclockwise order (clockwise would also do).
  2. For each edge of convex hull (i.e. every two consecutive points) calculate furthest point from the line containing the edge.
  3. Find the minimum of (2) and rotate accordingly (i.e. the line will be parallel to $OY$ axis).