0

Inspired by a childrens game.

Two points $p_1$ and $p_2$ are hidden at two random locations with real coordinates $(x,y)$ in a coordinate system. A point-like representation of you is placed at the origin. The objective is to find the coordinates of the two points.

$D$ = (the distance between you and $p_1$)$+$(the distance between you and $p_2$).

Rules:

You are allowed to move in the plane in any direction any length of distance.

The only sources of information is your position on the plane and wether $D$ is increasing, decreasing, or staying the same. This information is recieved continiously.

Questions:

Is there a method to always find the coordinates of $p_1$ and $p_2$?

What is the least number of times needed to change direction in order to guarrantee that the coordinates are found?

Notes:

For only one point, the least number of times needed to change direction is 3. For motivaton, see comments.

Similar to in the one-point case, the origin can in the two-point case be thought of as a point on a tilted ellipse with foci $p_1$ and $p_2$.

For the same sort of problem in one dimension on the number line: The cases with 1 and 2 points are trivial, but for 3+ points, it is impossible to find a general method.

For the same sort of problem in three dimensional space: The case with 1 point can be solved in a manner similar to the the case with 1 point in two dimensions by finding two cicles on the surface of a sphere centered at $p$. Will elaborate.

Ola
  • 617
  • 3
  • 16
  • Do you mean the coordinates to be integer, by any chance? – Ivan Neretin Apr 26 '17 at 14:45
  • @IvanNeretin Not nessiceraly. – Ola Apr 26 '17 at 15:08
  • Then how can it be solvable even in one-point case? – Ivan Neretin Apr 26 '17 at 15:15
  • 1
    @IvanNeretin The origin/you can be thought of as a point on a circle centered at $p$. http://imgur.com/a/I5ENB. By walking along either the x-axis or the y-axis, $D$ will decrease up to a certain point at where $D$ will start to increase. By changing direction with the angle $\pi/2$, you will start moving radially outwards or inwards. If you are walking radially outwards, you will have to make a complete turn and keep walking until $D$ starts increasing, at which point you stand on the coordinates of $p$. – Ola Apr 26 '17 at 15:53
  • Do you not have to test a direction to see which way you go to reduce $D$? Does that make possibly two extra turns? Also you have to be able to move continuously and continuously check increasing/decreasing, which isn't clear from the formulation. – Mark Bennet Apr 26 '17 at 17:06
  • @MarkBennet Testing does result in one extra turn (for the one point case) which in total results in 3 turns. Will clarify the continuous checking. – Ola Apr 26 '17 at 18:20

1 Answers1

2

This is a not quite checked proposal

Walk along the $x$-axis in the direction which reduces $D$ until it starts to increase. Then turn and walk parallel to the $y$-axis to reduce $D$. You will now be at a point on the line joining the two points. This line is the locus of minimum $D$. Now walk back out to the original $y$-axis and do the same with the directions reversed. I believe this should in general identify a second point on the line (there are exceptions*). Now walk the line and the two points where $R$ begins to increase from being constant are the ones you want.

* A line at $45^{\circ}$ through the origin will yield the same point from both walks and you need two to define the line. But you know the origin is on the line so you can walk it. What I haven't checked to my satisfaction is whether there are any other exceptions - in which case an answer would be to choose different axes.

Mark Bennet
  • 100,194
  • Is it guaranteed that you will land on the joining line? If so, then that's it! – Ola Apr 26 '17 at 18:56
  • @OlaB The locus of points at a combined distance $R$ from two fixed points in a plane is an ellipse, which degenerates into the straight line joining them as the minimum. The shortest distance from one point $A$ to another $B$ via a fixed line is found by reflecting $B$ in the line to $B'$ and the line joining $A$ to $B'$ cuts the fixed line in the point you need. This is necessarily "between" $A$ and $B$. There are special cases e.g. $AB$ perpendicular to fixed line, but you still find it. – Mark Bennet Apr 27 '17 at 07:08
  • I confirmed the solution algebraically. Thank you! I am interested in the general case with $n$ points in $d$ dimentions. Should i consider making a new post? – Ola May 05 '17 at 13:35