8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ How does one usually solve this? $\endgroup$
    – François G. Dorais
    Commented Jun 10, 2010 at 2:50
  • $\begingroup$ How do you formulate precisely the notion that the rope doesn't self-penetrate? $\endgroup$
    – Guy Katriel
    Commented Jun 10, 2010 at 6:46
  • $\begingroup$ 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]$. $\endgroup$
    – Roland Bacher
    Commented Jun 10, 2010 at 7:13
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 10, 2010 at 13:31

2 Answers 2

Reset to default
3
$\begingroup$

@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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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! $\endgroup$
    – Joseph O'Rourke
    Commented Nov 27, 2010 at 0:53
  • $\begingroup$ @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! $\endgroup$
    – Thierry Zell
    Commented Nov 27, 2010 at 5:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .