Take the 2-minute tour ×
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.

Suppose we are given $n$ segments $l_1,...,l_n$ in $\mathbb{R}^2$ such that $|l_i|=i,\ \forall\ i=1,...,n$, where $|l_i|$ is the length of $l_i$. Let $\alpha_1,...,\alpha_{n-1}$ be $n-1$ angles such that $\alpha_i>0$ and $\sum_{i=1}^{n-1}\alpha_i\leq\frac{\pi}{2}$.

Consider the following operation: (All angles are assumed to be "clockwise").

1) Place $l_{1}$ anywhere in $\mathbb{R}^2$,

2) Place $l_{2}$ at either of the end points of $l_{1}$, making an angle of $\alpha_{1}$,

3) Place $l_{3}$ at the end point of $l_{2}$ not occupied by $l_{1}$, making an angle of $\alpha_{2}$,

...

n-1) Place $l_{n-1}$ at the end point of $l_{n-2}$ not occupied by $l_{n-3}$, making an angle of $\alpha_{n-2}$,

n) Place $l_{n}$ at the end point of $l_{n-1}$ not occupied by $l_{n-2}$, making an angle of $\alpha_{n-1}$.

Now consider arbitrary permutations both of the angles $\alpha_i$ and of the lengths $l_i$. Which ordering of the angles and lengths maximizes the distance between the two endpoints of the chain of segments?

Edit: The problem in the form that it was stated in the first time was too general, hence I have changed some assumptions.

Thanks.

share|improve this question
    
The angles $\alpha_i$ must have the same orientation as the initial angles (i.e. maintain their clockwise/anticlockwise count)? –  Beni Bogosel Oct 27 '12 at 1:06
    
@BeniBogosel, a priori there is no restriction about this, but it is interesting to understand both cases. –  Tomás Oct 27 '12 at 10:28
    
The question seems interesting, but is way to general to give a precise answer. The idea is that the long segments must make an angle close to $\pi/2$ with the first segment. Have you tried at least the case of 3 segments and 2 angles? –  Beni Bogosel Oct 27 '12 at 12:08

1 Answer 1

Of course, one obvious answer is trying out all possible permutations. I might have something slightly better. Suppose that you have a fixed order of angles. I'm not sure how to obtain that, so for the moment you may assume that an outer loop iterates over all possible permutations of these.

Now consider unit vectors oreinted according to the cumulative angle sums, i.e. pointing into the directions your line segments would for a given orientation of the first line. Each vector of unit length has one component in $x$ direction and one in $y$. For the moment assume that your task is not to maximize the distance between the endpoints, but instead the $x$ coordinate of the end point. Then it is easy to assign lengths to the segments: the larger the $x$ component of the corresponding unit vector, the larger the length you want to assign to that segment. Thus finding the best order of lengths means simply ordering both lists, the one of your directions by $x$ coordinate, and then match them one to one.

Now suppose you turn the first line segment around in positive (counter-clockwise) direction. All the unit vectors will turn as well. If their $y$ component is negative, then their $x$ component will increase, while for positive $y$ component the $x$ component will decrease. So take your list of unit vectors ordered by $x$ coordinates, and look for pairs of subsequent vectors where the smaller one is increasing but the larger one is decreasing. At some angle, the two will ahev the same length, and after that angle, their order by $x$ component will have changed. Furthermore, for some angle the segment will reach $y=0$, after which its growth direction will reverse. So you can compute a set of possible angles where something interesting will happen. Take the smalled of all these numbers, and act on the interesting event: If it was one segment becoming equal in $x$ coordinate to another, then you can swap them in the ordered list. If it is one segment changing direction, then you can use the new direction to compute the next interesting events.

In this fashion, you can treat a whole rotation of the angle configuration by considering only a finite number of events where interesting things do happen. For each resulting configuration, you can plug in your actual lengths in order of increasing $x$ components, and look at the resulting distance. The global optimum might not be reached in $x$ direction when considering only the interesting angles, but the uninteresting angles between all share the same combinations, so by taking the actual euclidean distance incuding the $y$ coordinate, the optimum will be among the assignments you tried out.

This should be shorter than trying all permutations for both angles and lengths. Not sure whether there is a better way. I'm none too happy with the performance of my approach, but as I couldn't think of a better solution yet, and as noone else has answered this question either so far, perhaps the above solution is better than none at all.

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.