9
$\begingroup$

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. (Later: It's not; see below.) The right curve has lower curvature but strays exterior to $R$.
         

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

$\endgroup$
12
  • 1
    $\begingroup$ Note that if your points lie in an annulus $B_x(R)\backslash B_y(r)$ then $\kappa_{{\max}}\ge \tfrac1r$. $\endgroup$ Feb 26, 2012 at 21:21
  • $\begingroup$ @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. $\endgroup$ Feb 27, 2012 at 12:29
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 27, 2012 at 19:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan
    Feb 28, 2012 at 3:48
  • 1
    $\begingroup$ take a look at levien.com/phd/LevienSequinCAD09_014.pdf $\endgroup$
    – Will Jagy
    Feb 28, 2012 at 5:56

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.