10
$\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

Improve this question
$\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$
    – Anton Petrunin
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Garabed Gulbenkian
    Commented 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 ♦
    Commented Feb 28, 2012 at 3:48
  • 1
    $\begingroup$ take a look at levien.com/phd/LevienSequinCAD09_014.pdf $\endgroup$
    – Will Jagy
    Commented Feb 28, 2012 at 5:56

0

Reset to default

You must log in to answer this question.