3
$\begingroup$

Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by an angle $\alpha$

$$p_0=(0,0)$$ $$p_1=p_0+Rot[\alpha_1](1,0)$$ $$p_2=p_1+Rot[\alpha_1+\alpha_2](1,0)$$ $$...$$ $$p_j=p_{j-1}+Rot[\alpha_1+\alpha_2+...+\alpha_j](1,0)$$ $$...$$

We are constructing each point as the previous point plus the vector (1,0) rotated by the sum of all previous angles. All the edges of our polyline have the same length.

After n steps this curve may close up (it's unlikely if angles are random). Is there a smart strategy for finding whether there is a permutation of the angles that makes the curve close up? More generally, is there a good strategy to find the minimum distance of the last point from {0,0} over the set of all permutations? If not, what about approximations?

This problem sounds very natural to me but I was not able to find any references. I am far from being an expert in complexity theory and the way I came to formulate this problem is as a discretization of the smooth setting where arcs of a smooth convex curve are rearranged to make it closed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.