Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is the problem Coiling Rope in a Box decidable? To be specific, is this decidable?

Given $L > 0$ and $r \in (0,\frac{1}{2})$, both rational, can a rope of length $L$ and radius $r$ fit into a unit-cube box?

See the earlier MO question linked above for the problem definition.

It seems one would have to represent all possible rope curves with a finite set of parameters, and then use Tarski's quantifier elimination. But perhaps there are other routes to determining decidability.

share|improve this question
    
How does one usually solve this? –  François G. Dorais Jun 10 '10 at 2:50
    
How do you formulate precisely the notion that the rope doesn't self-penetrate? –  Guy Katriel Jun 10 '10 at 6:46
    
Is the following definition of a rope-coiling correct? A rope coiling of a rope of length $L$ and diameter $r>0$ is a smooth map $\gamma:[0,L] \longrightarrow \mathbb R^3$, parametrized by the length, such that $\parallel \gamma(s)-\gamma(t) \parallel \geq 2r$ if $\vert s-t\vert\geq r\pi$ and the curvature radius (given by the radius of the the tangent circle at a point which has to exist everywhere) of the path $\gamma$ is always $\geq r$. In order to fit into a unit box, such a rope coiling has to have all its coordinates in $[r,1-r]$. –  Roland Bacher Jun 10 '10 at 7:13
    
@Francois: I am sorry, I do not understand your question. @Roland: Thanks for trying to formalize it. I am uncertain if your conditions imply that the tubular neighborhood does not self-penetrate. A paper by Gonzalez and Maddocks says that as long as the radius of the circumcircle of every three distinct noncollinear points on the curve is $\ge r$, then self-intersection is avoided. –  Joseph O'Rourke Jun 10 '10 at 13:31

2 Answers 2

@Guy There are plenty of (more or less equivalent) definitions. One particular nice way is global radius of curvature introduced by Gonzalez and Maddocks in 1999.

share|improve this answer

Dear Joseph:

I do not have an answer to your question, just a somewhat involved comment, I hope you won't mind me putting it in the list of answers.

The quantifier elimination approach you describe seems reasonable, but it might be that you cannot solve the problem this way, and the reason why I think that is by comparison to another decision problem, that of connectedness of semialgebraic sets.

Early in the theory of semialgebraic sets, one notices that such a set is connected if and only if there is a semialgebraic path between any two points. Moreover, it is fairly clear that the (quantifier-free) description complexity (number of equations/inequalities, degrees etc) of such paths is bounded for any given connected component. So if we can bound the description complexity of these paths in terms of the description complexity of the original sets, we can then write a quantified formula that says "the set is connected", and, using quantifier elimination, we have our decision algorithm.

Problem: I do not know of any way of giving such an a priori bound.

There is an algorithm to solve the decision problem, the roadmap algorithm (see e.g. Ch. 15 in the book by Basu, Pollack and Roy. Note that, from the roadmap algorithm, it is possible to deduce a posteriori bounds on the description complexity of the semialgebraic paths, but only once the problem is already solved.

The moral of the story is that, even though quantifier elimination is a wonderful tool (a hammer in this case), it makes us want to look for nails that are not necessarily there: sometimes it's easier to just go ahead and solve the problem "by hand" (and if you've looked at roadmap stuff, it gets very subtle) than to spend a lot of time looking for a complexity bound that will let you bring down the hammer.

share|improve this answer
    
@Thierry: This is a compelling viewpoint. I am familiar with the roadmap algorithm, and I do see your point that it is likely difficult to bound the description complexity of a rope path. Thanks for the insight! –  Joseph O'Rourke Nov 27 '10 at 0:53
    
@Joseph: I hope I did not sound too pessimistic. My gut feeling is that the answer should be "yes". It sounds like a very nice problem, and the solution promises to be interesting, so best of luck! –  Thierry Zell Nov 27 '10 at 5:34

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.