# What is the minimum-curvature curve interpolating a given set of points in the plane?

We are given a set $$X$$ of $$n\ge 3$$ points in $$\mathbb{R}^2$$, belonging to the boundary of the convex hull of $$X$$ itself. Let $$\Gamma(X)$$ be the set of all convex, simple closed curves in $$\mathbb{R}^2$$ passing through all points in $$X$$ such that, at any point $$\mathbf{p}\in\gamma$$, there exists a normal vector $$\mathbf{n}_{\mathbf{p}}$$ and a tangent vector $$\mathbf{v}_{\mathbf{p}}$$ lying on $$\mathbb{R}^2$$. Let $$\kappa_{\mathbf{n}}(\mathbf{p})$$ the curvature of $$\gamma$$ at $$\mathbf{p}$$ in the direction of $$\mathbf{v}_{\mathbf{p}}$$.

I am looking for the name of the curve(s) $$\gamma\in\Gamma(X)$$ that minimizes the maximum curvature absolute value $$|\kappa_{\mathbf{n}}(\mathbf{p})|$$ over all points $$\mathbf{p}\in\gamma$$. I view it as a natural mathematical concept; therefore, I expect it is already mentioned in the related literature (although I could not find any reference yet).

Edit: After the discussion with SaúlRM and its answer, I added the constraint that $$\gamma$$ is convex.

Edit: After the comment of Yaakov Baruch, I added the constraint that all points of $$X$$ belong to the boundary of the convex hull of $$X$$ itself.

• I think it would be useful to give some extra conditions, e.g. the curves being contained in $S$. For example given a finite set of points in $\mathbb{R}^2$ it seems there are curves with arbitrarily low curvature passing through all the points Dec 9, 2022 at 16:13
• @MattF. as I just wrote in the comment for SaúlRM, informally speaking, the idea is very simple: I want to measure how curve must necessarily be (i.e., I am interested in the maximum curvature over all points of the curve itself) a curve passing through a given sets of points $X$ on a plane $P$, when $X$ belong to a convex polygon. Dec 9, 2022 at 21:07
• I think an optimal curve will be a union of line segments and circle arcs; if so, it should be easy to compute.
– user44143
Dec 14, 2022 at 21:46
• Is there a simple proof that the optimal curve through three points is a circle? It seems like it should be true but I don’t see a quick argument. I suppose that if the triangle is obtuse one can finding many minimizing curves, but it seems like there must be a circular arc through the vertices. Dec 16, 2022 at 18:24
• @PenelopeBenenati the thing is, I think the curve with minimal curvature, if it exists, is given by a sequence of arcs of circumference joining the points of $X$. However in the points of $X$, where the arcs of circumference meet, the curvature may not be defined, because the different arcs may have difference curvature. But if that's not a problem I'll try to write it in detail later Dec 18, 2022 at 12:33

As Matt F. says, his answer is not optimal, but the optimal solution, for most polygons (see (!!) below) comes from a similar construction using just arcs of circumference and segments. This answer gives a finite dimensional family of curves containing the optimal curve, thus reducing the problem to minimizing some functions (with explicit expressions) from $$[0,1]^n$$ to $$\mathbb{R}$$.

We will begin by studying which "convex" curves under certain boundary conditions (the initial/final positions and speeds) minimize curvature.

Fix $$(a,b)\in\mathbb{R}^2\setminus\{0\}$$ with $$a,b\geq0$$ and some unit vector $$v=(v_1,v_2)\in\mathbb{S}^1$$ with $$v_2>0$$, and let $$\Gamma$$ be the set of $$C^1$$ curves $$\gamma:[0,T_\gamma]\to\mathbb{R}^2$$ parametrized by arc length such that:

• $$\gamma(0)=(0,0)$$, $$\gamma'(0)=v$$, $$\gamma(T_\gamma)=(a,b)$$ and $$\gamma'(T_\gamma)=(1,0)$$.

• Let $$\alpha_{\gamma}(t)$$ be the angle that $$\gamma'(t)$$ forms with the positive $$x$$-axis. Then $$\alpha_\gamma(t)\in[0,\pi]\forall t$$ and $$\alpha_\gamma(t)$$ is decreasing.

An example of such a curve is given by $$c:[0,T_c]\to\mathbb{R}^2$$ formed by a circumference arc and a horizontal segment, as in the figure below. Such a curve $$c$$ is unique in $$\Gamma$$, and exists if $$\alpha(0)\geq\arccos(\frac{a}{\sqrt{a^2+b^2}})$$ (we will assume that is the case).

Claim: $$c$$ is the only curve of $$\Gamma$$ with least maximal curvature.

(If curvature is not defined everywhere, we can just interpret maximum curvature of $$\gamma$$ as the minimum Lipschitz constant of the map $$t\mapsto\gamma'(t)$$)

$$\textit{Proof of the claim:}$$ We will suppose that $$\gamma\in\Gamma$$ has less maximum curvature than $$c$$ and prove that $$\gamma=c$$. Both $$\alpha_\gamma(t)$$ and $$\alpha_c(t)$$ are decreasing, and the maximum curvature of $$\gamma$$ being less than that of $$c$$ implies that $$\alpha_c(t)\leq\alpha_\gamma(t)\forall t$$. Note that $$\gamma(t)=\left(\int_0^t\cos(\alpha_\gamma(t))dt, \int_0^t\sin(\alpha_\gamma(t))dt\right)$$ for any $$\gamma\in\Gamma$$.

So as $$\cos(\alpha_\gamma(t))\leq\cos(\alpha_c(t))\forall t$$ and $$a=\int_0^{T_\gamma}\cos(\alpha_\gamma(t))dt=\int_0^{T_c}\cos(\alpha_c(t))dt$$, we have $$T_\gamma\geq T_c$$. Now first suppose that $$\alpha_c(0)<\frac{\pi}{2}$$, so that $$\sin(\alpha_c)(t),\sin(\alpha_\gamma)(t)>0$$ for all $$t$$.

Then $$b=\int_0^{T_c}\sin(\alpha_c(t))dt\leq\int_0^{T_c}\sin(\alpha_\gamma(t))dt \leq\int_0^{T_\gamma}\sin(\alpha_\gamma(t))dt=b$$. So all the inequalities are equalities, meaning that $$\alpha(t)=\beta(t)\forall t$$, that is, $$c$$ and $$\gamma$$ are the same curve.

If $$\alpha(0)>\frac{\pi}{2}$$, the proof I found is more complicated, here is a sketch. let $$t_\gamma=\inf\{t;\alpha_\gamma(t)=\frac{\pi}{2}\},t_c=(\alpha_c)^{-1}(\frac{\pi}{2})$$. Then we can prove that $$\gamma(t_\gamma)-c(t_c)$$ has negative $$x$$-coordinate and, as above, deduce that $$T_c-t_c\leq T_\gamma-t_\gamma$$, so, letting $$y(p)$$ be the second coordinate of $$p\in\mathbb{R}^2$$, we get $$b-y(c(t_c))\leq\int_{t_c}^{T_c}\sin(\alpha_c(t))dt\leq\int_{t_\gamma}^{T_\gamma}\sin(\alpha_\gamma(t))dt=b-y(\gamma(t_\gamma))$$, with equality iff $$T_c-t_c=T_\gamma-t_\gamma$$ $$\alpha_\gamma(t_\gamma+t)=\alpha_c(t_c+t)$$ for all $$t>0$$.

We also have that $$t_c\leq t_\gamma$$, so $$y(c(t_c)) =\int_0^{t_c}\sin(\alpha_c(t))dt= \int_{\frac{\pi}{2}}^{\alpha_c(0)}\min\{t;\alpha_c(t)>\alpha\}d\alpha \leq \int_{\frac{\pi}{2}}^{\alpha_\gamma(0)}\min\{t;\alpha_\gamma(t)>\alpha\}d\alpha$$ $$=\int_0^{t_\gamma}\sin(\alpha_\gamma(t))dt=y(c(t_\gamma))$$, where the non trivial equalities come from Fubini (we calculate the area under the graph of the function horizontally instead of vertically). So finally, we have $$b=y(c(t_c))+(b-y(c(t_c)))\leq y(\gamma(t_\gamma))+(b-y(\gamma(t_\gamma)))=b$$, with equality iff $$\alpha_c(t)=\alpha_\gamma(t)$$ for all $$t$$, so $$c=\gamma$$. $$\square$$

Now back to the question: suppose that we have a convex curve $$\gamma$$ passing through all the points of $$X$$ (the points of $$X$$ are the vertices of a polygon $$\mathcal{P}$$, and maybe some additional points in edges of $$\mathcal{P}$$). Let $$x,y$$ be points of $$X$$ that appear consecutively in $$\gamma$$, with $$\gamma(a)=x$$, $$\gamma(b)=y$$ for some $$a,b$$. We can find some curve $$f:[a,b]\to\mathbb{R}^2$$ going from $$x$$ to $$y$$, with $$f'(a)=\gamma'(a)$$, $$f'(b)=\gamma'(b)$$ and such that $$f$$ has less curvature that $$\gamma$$ in [a,b].

(!!) We can only apply the claim when the sum of the two angles $$\gamma$$ forms with each side is $$<\pi$$ (indeed, in the claim the angle $$\alpha(t)$$ has a total variation $$<\pi$$). However if the sum of the angles in the claim was $$\pi$$, we can extend the curve by segments without increasing the curvature, and if it is $$>\pi$$, we can achieve arbitrarily low curvature using the same trick. From now on we will assume that these sums of angles are $$<\pi$$. This is always true for polygons in which the sum of any two consecutive exterior angles is $$<\pi$$ (this is not a very restrictive condition, as all exterior angles add up to $$2\pi$$), but it may not work with triangles for example.

We can summarize this in the following result:

For any convex convex curve $$\gamma$$ passing through the points of $$X$$, there is another convex curve $$f$$ passing through the points of $$X$$ such that:

• $$f'(x)=\gamma'(x)\;\forall x\in X$$.
• The arc of $$f$$ between any two consecutive points $$x,y\in X$$ is formed by a segment and/or an arc of circumference.
• $$f$$ has less maximal curvature than $$\gamma$$.

In fact the curve $$f$$ is uniquely determined by the values of $$\gamma'(x)$$ for each $$x$$ in $$X$$. So what we have to do is look for the values of $$\gamma'(x)$$ for each $$x$$ in $$X$$ which make the maximal curvature of $$f$$ be minimal.

We can also use this to prove that the curve with min-max curvature exists: first of all, let $$\mathcal{E}$$ be the set of edges of $$\mathcal{P}$$, and let $$\mathcal{A}\subseteq\mathcal{E}$$ be the subset of edges of $$\mathcal{P}$$ contained in $$\gamma$$; then $$\mathcal{A}$$ can only take finitely many values, and for each one we can prove that there is a curve of min-max curvature using a compactness argument (curvature depends continuously on the values $$f'(x)$$ for $$x\in X$$, except when $$f'(x)$$ is parallel to a segment of $$\mathcal{P}$$ containing $$x$$, and when $$f'(x)$$ approaches that segment the curvature gets large so we don't care).

So to minimize the maximal curvature you can, for each value of $$\mathcal{A}$$, write the maximal curvature of $$f$$ in terms of the angles $$f'(x)$$ forms with the sides of $$\mathcal{P}$$, and then the problem essentially becomes minimizing some functions with domain $$[0,1]^n$$. Probably dividing in cases depending on $$\mathcal{A}$$ of edges contained in $$\gamma$$ will be unavoidable, but I'm sure there is some way to make this more efficient than just checking all the subsets $$\mathcal{A}$$.

Edit: I decided to add the explicit expression of the radius of curvature.

Suppose that $$l$$ is a side of $$\mathcal{P}$$ with length $$x$$ and the convex curve $$c$$ formed by segments and arcs of circumference is like in the figure below, forming angles $$\alpha\geq\beta$$ (with $$\alpha+\beta<\pi$$) with the side $$l$$.

Then it's not difficult to check that the radius of curvature of the circumference arc is $$x\frac{\sin(\beta)(1+\cos(\alpha+\beta))}{\sin(\alpha+\beta)^2}$$. Note that for fixed $$\alpha+\beta$$, the minimum curvature is achieved for $$\alpha=\beta$$, and in the case $$\alpha=\beta\geq0$$, the curvature increases with $$\alpha$$.

Claim: If the points of $$X$$ are in a circumference and the condition in (!!) is satisfied, then $$c$$ achieves min-max curvature.

$$\textit{Proof:}$$ Let $$\gamma$$ be a $$C^1$$ convex curve containing all points of $$X$$ which minimizes maximal curvature. For each side $$l$$ let $$\alpha_l=\beta_l$$ be the angles that $$c$$ forms with $$l$$, and let $$\alpha_l'\geq\beta_l'$$ be the angles that $$\gamma$$ forms with $$l$$. Then $$\sum_l\alpha_l+\beta_l=2\pi=\sum_l\alpha_l'+\beta_l'$$. But for each $$l$$ we have $$\alpha_l+\beta_l\geq\alpha_l'+\beta_l'$$, because $$\gamma$$ minimizes curvature, so $$\alpha_l+\beta_l=\alpha_l'+\beta_l'$$ for all $$l$$. Again, as $$\gamma$$ minimizes curvature, we need to have $$\alpha_l'=\beta_l'$$ for all $$l$$, so $$\gamma=c$$ as we wanted. $$\square$$

• The expression for the radius of curvature can be nicer using $$\cot(\frac{\alpha+\beta}2)=\frac{1+\cos(\alpha+\beta)}{\sin(\alpha+\beta)}$$ (and by naming the length with a letter that doesn’t look like a derivative).
– user44143
Dec 20, 2022 at 13:58

(This answer was posted before the convexity condition on the curve $$\gamma$$ was added to the question)

Suppose you have any finite set of points in $$\mathbb{R}^2$$, and rotate $$\mathbb{R}^2$$ so that they have pairwise distinct $$y$$-coordinates. Then we can create curves with arbitrarily low curvature passing through all the points. Here is an idea of what they would look like:

You can make the curves from the sides arbitrarily large, thus making their curvatures arbitrarily small.

• Thank you ! I see the point. I should simply add the constraint that $\gamma$ is convex. I guess I have to make another post. On the other hand, I think such convex curve passing through a set of points $X$ should have already be studied, but it seems there are not reference about it anyway. Dec 9, 2022 at 21:35
• Yes, that constraint would make the problem more interesting :) you can just add it to the question, I won't be offended or anything Dec 9, 2022 at 21:36
• Ok, thank you a lot! :) Dec 9, 2022 at 21:36
• SaúlRM, in your opinion should I simplify the whole text by talking only about curves in $\mathbb{R}^2$? Dec 14, 2022 at 18:55
• I think that would be a good problem to begin, and it is much easier to state. I thought a bit about that case but I didn't find anything special Dec 14, 2022 at 18:57

Here is one limit on the curvature needed. It is not optimal, but it is explicit, and probably a good starting point for numerical or theoretical optimization.

Proposition: Consider the convex hull of the vertices as a polygon; then there is a path through the vertices with curvature of at most $$\max_i \frac{1+\cos(t_i+u_i)}{s_i\cos(\max(t_i,u_i))}$$ where $$s_i$$ is the length of the side and $$t_i$$, $$u_i$$ are half the angles at its vertices.

The path will go through each vertex in a direction perpendicular to the angle bisector at that vertex.

Proof: For consecutive vertices $$V,W$$, take their angle bisectors, and let the perpendiculars to those bisectors intersect at $$S$$.

Let triangle $$SVW$$ have side lengths $$s,v,w$$ and assume wlog that $$v\le w$$. Let $$V’$$ be the point on $$SV$$ with $$VV’=w-v$$.

Then our path will go through the line segment $$VV’$$, and a circular arc through $$V’$$ and $$W$$ which is tangent to $$SV$$ and $$SW$$. Since this section of path is perpendicular to the angular bisector at each vertex, it will have the same direction at each vertex as the path from the other side, and our final construction can combine these path sections for all sides.

If $$t$$ and $$u$$ are the angles between the convex hull and the respective angle bisectors at $$V$$ and $$W$$, then the angle at $$S$$ is $$t+u$$. So the radius of the circle arc is $$v\tan(\frac{t+u}2)$$ and by the law of sines this is $$\frac{s \cos t}{\sin(t+u)}\ \tan(\frac{t+u}2)$$ We can rewrite $$t$$ as $$\max(t,u)$$ because $$v\le w$$, and rewrite $$\tan(\frac{t+u}2)/\sin(t+u)$$ as $$1/(1+\cos(t+u))$$. Then inverting the rewritten radius gives the original expression in the formula for the curvature. $$\square$$

Example:

[]

Let the vertices be $$(\pm2,\pm1)$$ and $$(\pm3,0)$$. Then each side length is $$\sqrt{2}$$ or $$4$$, and each vertex half-angle is $$\pi/4$$ or $$3\pi/8$$. So the curvature is $$\max(\frac{1+\cos(\frac{5\pi}8)}{\sqrt{2}\cos(\frac{3\pi}8)}, \frac{1+\cos(\frac{3\pi}4)}{4\cos(\frac{3\pi}8)})$$ which gives $$\sim1.14$$.

The apparent minimum possible maximum curvature for this example is $$1$$, achieved by the union of two vertical semicircles and two horizontal lines.

• Thank you for your detailed answer. Interesting observations! Dec 18, 2022 at 10:02
• Thanks! Now it is less detailed and better.
– user44143
Dec 18, 2022 at 19:27
• @BeniBogosel, I allow discontinuities in the curvature but not in the tangent. This seems reasonable to me, and probably any limit of smooth approximately-optimal curves would be of this form.
– user44143
Dec 18, 2022 at 23:07
• @MattF. another way to interpret it as defining "maximum curvature" as the minimum Lipschitz constant of the function $t\mapsto \gamma'(t)$ Dec 19, 2022 at 1:47