Mathematics desk
< April 29	<< Mar \| April \| May >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 30

Distance between two curves

If I have 2 arbitrary but smooth curves (equations would exist), how can I determine a point on each curve that results in the minimum distance between the two points.

If I knew one point, I could calculate the distance to each point on the other curve and look for a minimum. But I don't see how to do it with two variables.

For the purposes of this question, assume two circles with different centres and radii that do not intersect and do NOT use the fact that we can determine the points by constructing a line between the two centres.

Thanks -- SGBailey (talk) 10:44, 30 April 2019 (UTC)[reply]

I will answer the question assuming you are new to optimization problems, as I guess from your assertion that you would know how to solve the problem if there was only one variable but not with two. Please accept my apologies and provide a tad more detail if that is not the case.

Denoting by

d(x,y)

the distance between the point at coordinate x on the first curve and y on the second curve, the question is to find the minimum of that function of two variables. If we ignore for a moment that the function to minimize has a geometrical definition, we are facing a standard optimization problem. An overly simplified summary of the field is that it is extremely easy to find a minimum even for pathological functions but extremely hard to ensure it is not a local minimum even for well-behaved ones.

For an example of an optimization algorithm, see our decent article about gradient descent. For code libraries, Python's scipy.optimize implements all common optimization algorithms.

Now: can we take advantage of the additional information on d to make the optimization run faster/better? Probably. Is it worth it? You tell us, depending on runtime constraints and the like. Tigraan^{Click here to contact me} 12:51, 30 April 2019 (UTC)[reply]

- The standard tool for problems of this sort is the method of Lagrange multipliers, particularly with multiple constraints: Lagrange_multiplier#Multiple_constraints. There the equation of one curve (involving variables with one set of names, like x and y) is one constraint, the equation of the second curve (involving an independent set of variables, like w and z) is the other constraint, and the distance (a function of all four variables) is the quantity being minimized. Often for distances it is easier to use the square of the distance. This reduces the problem to pure algebra, but it may or may not be tractable depending on your curves.
- In some cases, it is also possible to treat this as two chained single-variable optimization problems: first optimize with respect to one variable, treating the other as a constant, then substitute and optimize with respect to the remaining variable. --JBL (talk) 13:26, 30 April 2019 (UTC)[reply]

In this case you can simplify things a bit by assuming that the tangent lines at the two points are parallel and both lines are perpendicular to the line connecting the two points. (Pretty sure Lagrange multipliers will tell you this eventually.) Note that the same condition applies to pairs of points at maximal distance and various local extrema, so you need another step to find which pair of points is the one you want. According to my calculations the resulting system would have 4 (non-linear) equations and 4 unknowns so working it out algebraically might be tricky. --RDBury (talk) 17:23, 30 April 2019 (UTC)[reply]

More specifically, if the curves are given by f(x, y) = 0 and g(x, y) = 0 then the points (x₁, y₁), (y₂, x₂) satisfy the simultaneous equations

f(x_{1},y_{1})=g(x_{2},y_{2})={\begin{vmatrix}f_{x}(x_{1},y_{1})&f_{y}(x_{1},y_{1})&0\\x_{1}&y_{1}&1\\x_{2}&y_{2}&1\\\end{vmatrix}}={\begin{vmatrix}g_{x}(x_{2},y_{2})&g_{y}(x_{2},y_{2})&0\\x_{1}&y_{1}&1\\x_{2}&y_{2}&1\\\end{vmatrix}}=0

--RDBury (talk) 18:49, 30 April 2019 (UTC)[reply]

We can simply assume that these two curves are specified parametrically as

\mathbf {x} _{1}(s_{1})

and

\mathbf {x} _{2}(s_{2})

. Then the distance squared is

D^{2}=(\mathbf {x} _{1}(s_{1})-\mathbf {x} _{2}(s_{2}))^{2}

.

Now stationary points can be found from the system

\left\{{\begin{array}{lcr}{\frac {\partial D^{2}}{\partial s_{1}}}&=&2(\mathbf {x} _{1}(s_{1})-\mathbf {x} _{2}(s_{2})){\frac {d\mathbf {x} _{1}(s_{1})}{ds_{1}}}=0\\{\frac {\partial D^{2}}{\partial s_{2}}}&=&-2(\mathbf {x} _{1}(s_{1})-\mathbf {x} _{2}(s_{2})){\frac {d\mathbf {x} _{2}(s_{2})}{ds_{2}}}=0\end{array}}\right.

Ruslik_Zero 19:28, 30 April 2019 (UTC)[reply]

I took the liberty of fixing your parentheses, but otherwise that's an analytic statement of the geometrical conditions on the tangent lines above, though I probably would have used a ⋅ to indicate dot product. I was thinking about it more geometrically but it works out nicer the way you did it. I should have mentioned it above but the cases where both points are the same point of intersection of the curves appear as solutions to the equations. The distance is then 0 but I'm not sure that's what the OP had in mind. --RDBury (talk) 13:09, 1 May 2019 (UTC)[reply]

Thx all. -- SGBailey (talk) 11:11, 2 May 2019 (UTC)[reply]

@SGBailey and Tigraan: As an example for difficult judgement on simple curves let's consider a circle within an ellipse (or vice versa), being almost concentric. A small change in their relative position can switch the global minimum from one apex (a local minimum) to another.

Two concentric circles present another difficulty: they're equally distant from one another everywhere, but you (i.e., your algorithm) will never know if they were actually analyzed 'everywhere'; it's always possible there is some elbow on one of them, which was not detected bit which will make a sharp minimum. --CiaPan (talk) 20:48, 6 May 2019 (UTC)[reply]

???? The hypothesis of the question includes (in the very first sentence) the statement that equations for the curves are known. This could mean different things (I took it to mean an implicit equation, Ruslik took it to mean parametric equations), but all of them confer absolute knowledge of the entire curve. And there are three or four complete correct answers above your post. --JBL (talk) 21:57, 6 May 2019 (UTC)[reply]

???? I don't know what the 'absolute knowledge of the entire curve' is and, even when I try to imagine it, I still have no idea how it might be implied by the knowledge of the equations. For example, most people don't see a four-leaf structure in the equation

(x^{2}+y^{2})^{3}=4x^{2}y^{2}

of quadrifolium or an hour-glass in the equation of a Cassini oval. Anyway, the problem is not in knowing the equations, because we all know the equations are known. The problem is in that 'stationary points are solutions of the system' presented by Ruslik does not necessarily imply 'stationary points can be found from the system'. Imagine a spiral like this one and a circle below it – they have a countably infinte set of local minima. Can you find the global one just by analyzing the Ruslik's system of equations? Similar problem with a sine of 1/x with a circle centered at Y axis.
My point is: the problem has no simple solution in general. And my examples with circles and ellipses show that; in a simplest way I could find. --CiaPan (talk) 17:42, 8 May 2019 (UTC)[reply]