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
    The minimal $x$-width in your example would be smaller than the distance between $A$ and $B$. A slight rotation makes one of the long sides vertical, and this produces a smaller $x$-width, say from $A$ to its opposite side. Generally, you should look at the perpendicular distance between the longest side and the opposite vertex.2012-03-15
  • 0
    I think its just worded in a confusing way. The minimum x width could be, but there is no way to rotate the shape where the distance between the western most and eastern most points will be less than the distance between A and B.2012-03-15
  • 0
    @nsfyn55 what about rotation such that $B$ and $C$ will have the same $x$ coordinate?2012-03-15
  • 0
    @nsfyn55 ok, can we rotate by any angle, or do we need that all the coordinates $\in \mathbb{Z}$?2012-03-15
  • 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