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

I have $n$ points $p_i$ strictly interior to a rectangle $R$, and I would like to connect them with a curve $C$ whose curvature is as low as possible. Let $\kappa_\max(C)$ be the sharpest (largest absolute value) of the curvature of $C$ at any point along $C$. More specifically, $C$ should: (a) pass through the points in any order; (b) be simple, i.e., non-self-intersecting; (c) remain inside $R$; and (d) have the minimum $\kappa_\max(C)$ over all $C$ satisfying (a,b,c).

For example, perhaps the curve left below is optimal. The right curve has lower curvature but strays exterior to $R$.
          B
oundedCurvature

I am seeking a lower bound on the minimum of $\kappa_\max$, as a function of the point configuration and its placement within $R$. I have seen literature bounding curvature variation, and literature focused on shortest paths of bounded curvature, and literature that permits $C$ to self-cross, but no literature on my specific collection of constraints. My $n$ is not large, so a solution for a fixed permutation would still be quite useful. If anyone can point me to relevant literature, I would appreciate it. Thanks!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature
And here is Scott Carnahan's improvement to my example, left:
                    Improvement

share|improve this question
1  
Note that if your points lie in an annulus $B_x(R)\backslash B_y(r)$ then $\kappa_{{\max}}\ge \tfrac1r$. –  Anton Petrunin Feb 26 '12 at 21:21
    
@Anton: Thanks! However, if the points in the annulus happen to lie on a nearly collinear arc, they could be captured by that low-curvature arc. –  Joseph O'Rourke Feb 27 '12 at 12:29
2  
You might be interested in questions 19074 and 22601 as well as some of the answers given to them even though the sort of minimizing curve sought for in these questions is of the "y=f(x)" type. With regard to your question, it occurs to me that if your curve C was the arc of a spiral enclosing a sufficiently large portion of the Euclidean plane, the maximum absolute value of its curvature at any point might be made arbitrarily small while all your n points could still be points of C. Of course this would violate your condition (c) unless your rectangle R was large enough. –  Garabed Gulbenkian Feb 27 '12 at 19:44
1  
It looks to me like the ordering 5-4-2-1-3 could yield a lower curvature path. In particular, it might be best to avoid points of inflection whenever possible. –  S. Carnahan Feb 28 '12 at 3:48
1  
take a look at levien.com/phd/LevienSequinCAD09_014.pdf –  Will Jagy Feb 28 '12 at 5:56

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.