0
$\begingroup$

Consider two points in $\mathbb{R}^d$, $A$ and $B$.
Now, consider two scalar quantities, $x$ and $y$.
I want to find the point in $\mathbb{R}^d$ that is closest to being $x$ distance from $A$ and $y$ distance from $B$

Here's what I believe is the mathematical representation of what I'm trying to say, but if it still doesn't make any sense, I attached an image below just to demonstrate a simpler example in 2D.

$\displaystyle\min_{\forall m \in \mathbb{R}^d} \mbox{ } |\|A - m\| - x| + |\|B - m\| - y|$

Just to recap, I want a way, given the coordinates of two points, $A$ and $B$, in $\mathbb{R}^d$, of finding the point which is $x$ distance from $A$ and $y$ distance from $B$. If no such point exists, I want the point that if closest to satisfying this.

$\endgroup$
6
  • $\begingroup$ "The closest" has no predefined meaning here and can be defined in many different and reasonable ways, including a variation of what you wrote here (you probably wanted absolute values instead of parenthesis in your equation, ie. $\min |\|A-m\|-x| + |\|B - m\| - y|)$. An equally reasonable way of expressing the closest would be $\min |\|A-m\|-x|^2 + |\|B - m\| - y|^2$ which has the nice property of being differentiable everywhere. It will be up to your application really $\endgroup$
    – MBW
    Jul 2 '20 at 21:59
  • $\begingroup$ Just a quick drunken idea that I don't have the clarity of mind to prove formally: If the balls $B(A, x)$ and $B(B, y)$ intersect, take one such intersection point to get an optimal result. Otherwise consider the straight line $AB$ between $A$ and $B$ and take the midpoint of the line connecting the intersection of $AB$ with $B(A, x)$ and $B(B, y)$. Also the comment by @MBW is right, I went off the example you posted. $\endgroup$ Jul 2 '20 at 21:59
  • $\begingroup$ @MBW Yes, sorry, I actually meant to write absolute value, as you said. Let me update it $\endgroup$
    – Ryan Rudes
    Jul 2 '20 at 22:00
  • $\begingroup$ Also please let me know if anything I said does not make sense to you, but if you interpret it geometrically I think my idea is at least close. $\endgroup$ Jul 2 '20 at 22:02
  • $\begingroup$ @Watercrystal your method minimizes the function given by the OP, but you don't need to take a midpoint. All points in the line going from $A$ to $B$ outside both spheres will have the same value. If no such point exists, then either they intersect and an intersection will have the value 0 as you say or one is contained in the other and you need to any point in the segment outside the smallest sphere that doesn't contain the center of the other sphere (a drawing would really help here, sorry!). In particular, a solution will always be in one of the spheres so you only need to check two poin $\endgroup$
    – MBW
    Jul 2 '20 at 22:15
0
$\begingroup$

We are gonna have 3 cases. Here is a picture in $\mathbb R^2$:

enter image description hereIf the surface of these balls intersect, i.e. $|x-y|<|A-B|<x+y$, then we have exact solutions. In fact there is an entire space of solutions which looks like $S^{d-1}$. In the plane, we get the pair $M_1$ and $M_2$.

The second case is $|A-B|>x+y$. (Sorry the image is out of order). This is when the balls do not intersect. Given a point $m$, we are trying to minimize the discrepancy between $|m-A|$ and $x$, also the discrepancy between $|m-B|$ and $y$. This occurs along the line segment $PQ$ which I drew in the figure, as @MBW noted any point along that line segment is a minimum for $f(m)$.

Third case is $|A-B|<|x-y|$. Then the circles are "too close" so to speak. Assume without loss of generality the ball around $A$ is contained inside the ball around $B$. Then any point along the line segment $BP$ as depicted will minimize the distance.

If you want this to have a unique solution then replace $f(m)$ by $$ f^\star(m) = ||A-M|^2-x|^2 + ||B-M|^2-y|^2 $$ For this function, in the first case, there is still a space of exact solutions. In the second and third case, along the line segment which was considered, take the midpoint.

Edit: There is one error in the figure, on the third figure, the point P should actually be reflected across the point $A$, and instead of $BP$ we consider the segment $PC$ where $C$ is the intersection of the ray $BA$ and the ball centered at $B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.