Sorry if this is a silly question, but: imagine there are two agents on a finite 2d plane. Each agent knows her location but not the other's, and they want to find the relative directions between them (i.e. agent A wants to find unit vector in direction of agent B and vice versa), without compromising their locations. The agents communicate directly (so can't use a 3rd party that will have both their locations and provide the directions). Is there a protocol that the agents can use? I feel like there's a very simple solution I'm missing.
My first approach was to try to converge on a distant point to which they share direction, but couldn't think of a way to compare directions to the distance point without exposing their locations after two iterations (maybe something with locality-sensitive hashing?)
Another approach was using homomorphic encryption, but again I couldn't figure how to have both locations encrypted by the same key to perform the calculation.
Thanks!
Edits in response to comments:
There aren't sensors capable of physically inferring the direction, the agents only have a digital communication channel (e.g. two mobile devices communicating over the internet).
As for leaking information, some information about the location (the direction) has to be compromised as @obareey mentioned, and it's also fine if some information about the distance leaks, as long as there's a way to limit this leakage while still calculating an accurate direction.
I'm more interested in the information-communication aspect than the physical aspects. So the situation is similar to having two computer programs wanting to find relative directions in some shared conceptual plane without exposing individual positions.
The one-dimensional version of this problem, where A and B each have a number and they want to decide whose number is greater, is Yao’s millionaires’ problem with various known solutions.
We can reduce the two-dimensional problem to the one-dimensional problem as follows. Let $\vec v$ be an arbitrary unit vector, say $(1, 0)$. Agent A at position $\vec a$ computes $x = \vec a \cdot \vec v$, and agent B at position $\vec b$ computes $y = \vec b \cdot \vec v$. They use the one-dimensional protocol to decide which of $x$ or $y$ is greater. This narrows the direction to a 180° range without revealing any other information. They now replace $\vec v$ with a unit vector perpendicular to the middle of this range and repeat the protocol, narrowing the direction to a 90° range. They continue in this way, bisecting the range at each step, until the direction is determined to within a desired tolerance.