Skip to main content
Image links broken; now fixed.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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$.
          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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpgBoundedCurvature
And here is Scott Carnahan's improvement to my example, left:
                    Improvement http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvature1.jpgImprovement

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg
And here is Scott Carnahan's improvement to my example, left:
                    Improvement http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvature1.jpg

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

added 244 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg
And here is Scott Carnahan's improvement to my example, left:
                    Improvement http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvature1.jpg

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg
And here is Scott Carnahan's improvement to my example, left:
                    Improvement http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvature1.jpg

Illustrating Anton's annulus idea.
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg

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!

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!

Addendum. Here is what I gather must be Anton Petrunin's idea:
                    BoundedCurvature http://cs.smith.edu/~orourke/MathOverflow/BoundedCurvatureAnnulus.jpg

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading