Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
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. – alex.jordan Mar 15 '12 at 17:56
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. – nsfyn55 Mar 15 '12 at 18:05
@nsfyn55 what about rotation such that $B$ and $C$ will have the same $x$ coordinate? – dtldarek Mar 15 '12 at 18:17
@nsfyn55 ok, can we rotate by any angle, or do we need that all the coordinates $\in \mathbb{Z}$? – dtldarek Mar 15 '12 at 18:28
@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. – alex.jordan Mar 15 '12 at 20:35

1 Answer

up vote 2 down vote

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).
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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