Shortest distance between two general curves using matlab
Given two functions: $F(x)$ and $G(x)$ is there is a way to find out the shortest distance between $F(x)$ and $G(x)$ provided we know that they do not intersect. I tried to consider parametric points on the two curves and applied the distance formula.The obvious step was then to minimize the function. However there are two problems: one is that it is quite tedious to differentiate the distance function and the foremost problem is that the function does is not a single variable function. Given these issues could anyone provide some insight into this problem?
$\endgroup$ 33 Answers
$\begingroup$To answer, I assume $F(x)$ and $G(x)$ are continuous in $I \in \mathbb{R}, I = [a,b]$. For simplicity, let $F(x)=f, G(x) = g, H(x) = h = f-g$. By symmetry I can assume $f \ge g$. Now consider the function $h(x)$:
- if $\exists x | h(x) = 0$, it means that there is a point $x$ such that $f(x) = g(x) \Rightarrow ||f(x) - g(x)|| = 0$ and so the minimum shortest distance between $f$ and $g$ is 0
- else, find the minimum value of $h$ (by letting $h'=0$): let's call the minimum $m$. Let $P$ be the point found intersecating $f$ and the normal (i.e the tangent to the tangent to the curve) to $g$, and $N$ vice-versa (please, take a look at the image below). You need to fix a point $a$ on $f | P \le a \le f(m)$ and a point $b$ on $g| g(m) \le b \le N$, then the shortest distance is $\min[||a-b||]$.
There are several ways to solve this kind of problem: the choice of methods depends on the details of the two functions/curves. I will assume here you mean the usual definition of distance between two curves, where the given line segment may not be vertical.
1) As you suggest, parameterize the two curves, find the distance function between two points--one on each curve--and minimize the distance function. As you write, this will be a function of two independent variables, so you need to use multivariable calculus.
2) Use Lagrange multipliers. This will involve (I think) four independent variables: $x$, $y$, and one for each curve. This is even more multivariable.
3) Given common assumptions, the line segment of minimal length between the functions is perpendicular to the tangent line at each function. You could then parameterize the normal lines for each function and find which lines are common to both curves. You may get more than one, but there are probably finitely many, so choose the normal lines that give the smallest distance.
4) There are also combination strategies, such as finding the normal lines to one curve, finding the intersection of each line with the other curve, finding the resulting distance, and minimizing that expression. This strategy avoids multiple variables.
$\endgroup$ 3 $\begingroup$One method that should find a local minimum (or maximum) distance between two curves involves solving two equations for two unknowns.
Assume two continuous, non intersecting functions, f(x) and g(x), with one line that intersects each curve normally at coordinates (x1, f(x1) and (x2, g(x2))
Equations: // comments
$f'(x_1)= g'(x_2)$ // intersecting line normal to curves --> slopes at intersections must be equal.
$x_1/f'(x_1) + f(x_1) = x_2/g'(x_2) + g(x_2)$ //y intercept for the line must be equal.
Solve for x1 in terms of x2 using equation 1.
Substitute x2 into equation 2 and solve for x2 algebraically or using numerical methods.
Solve again for x1 using equation 1.
This should yield $(x_1, f(x_1)), (x_2, g(x_2))$ and an equation for the normal line if desired.
Example: $f(x)=\sqrt(x), g(x)=x^2 + 1$, normal line (along minimum)
$\endgroup$
