Skip to main content
1 of 4
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Interpolating points with minimum curvature constraint

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 http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvature.jpg

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!

Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958