3
$\begingroup$

Okay so first of all I tried to make the title to sound like I understand something about mathematics, correct me if I am wrong with it.

Backstory / context:

I bumped into this problem when me and my friend were talking one night in discord about where my friend should order a pizza from. He then sent me a screenshot of the choices he had, but it was only showing two pizza places with distances to them, as each pizza place has some max delivery radius set. Suddenly a light went on in my head and I told my friend that if I he had sent me a third pizza place in the screenshot, I could find out where he lives based on the locations of the pizza places and the distances shown.

So then he sent me a picture of a third pizza place and I got to work. I have heard about triangulation before so I thought that it would be a good idea to read about how that works, but in the end I either did not understand the idea or the idea of triangulation is basically that I "kind of" know where I am, but I just don't know where that location is on the map, but since I had no idea about where this said friend lived, I came into conclusion that I don't have enough data for triangulation.

So the next thing I did was what felt like the second obvious one to me - I drew a circle around each pizza place with the distances as the circle's radiuses, probably because that is how they find people in CIA-style TV-shows. Well that did basically nothing, now I just had a VERY vague area where he might live aka. where all three circles overlap I guess.

So on I went to the third obvious thing, which was to draw a triangle through the pizza places. I then googled about finding a triangle centroid and got pretty convincing results. I figured that since the centroid point is inside all of the three circles I drew - this has to be where my friend lives. I then sent an image of my solution to my friend ready to receive applauds.

Well my solution was completely wrong. Not even close. I understand that the distances to the pizza places were probably calculated via roads and not with straight lines, so that might give me some error, but the solution of mine was too far off to blame it on error.

Unfortunately I like my and my friend's privacy, so I am not going to post an image of the original problem, but instead I spend some time in photoshop and created a fake scenario:

fake scenario

  • Distances are not actually meters, but pixel values photoshop gave me
  • Green dot is the answer, or where my fake friend lives. This point is actually unknown.
  • The pizzas are locations of fake pizzerias. These are known.
  • The pink lines are the distances to the pizzerias as given by the website
  • The cyan and the red lines, as well as the red midpoint dots and the blue centroid dot are parts of my solution or what I have tried to do to find the green point

So how can we find the green point (where my friend lives)? Can it even be found?

In mathematical terms, like said in the title, I guess this is a question about finding an originating point for three vectors of which lengths and directions we know.

(If someone finds a use for it, I can provide the .psd file of the map image)

$\endgroup$
2
$\begingroup$

Assuming that the 3 pizza places have coordinates $$c_1 =(x_1,y_1), c_2 =(x_2,y_2), c_3=(x_3,y_3)$$ and distances to your friend's location $r_1, r_2, r_3$ respectively then your friend's location is at a point where the 3 circles defined by those centers and radii intersect. It is possible that the intersection set of 3 circles is empty, in which case the given distances/locations of the places are incorrectly given (or there's a small error in which case you should try to find an intersection with rings that serve as a circle with a 'thickness' $\epsilon$ to account for measurement error, another possibility being trying to find the closest point to all circles when the initial data is not entirely accurate). It is also possible that there are infinitely many such intersection points, when the 3 circles coincide - then your friend's place can be at any point on the circle. Finally it's possible that 2 circles coincide and the third intersects them at 2 locations. In this case your friend's place can be in any of these two locations. Notice how you get more than one solution only when you actually have less that 3 circles, since coinciding such give no extra information. Finally this problem is probably more interesting in $\mathbb{R}^n$. In 3d for example 2 spheres would intersect (if they do not coincide and the intersection is not empty) such that you get a circle. A circle intersected with another sphere would yield (if it's not on the surface of the other sphere) 2 points. Finally you'll need another sphere to bring it down to one point. By a similar logic I assume that in $\mathbb{R}^n$ you will need $n+1$ hyperspheres in the general case. Note that in degenerate cases you will get more than one solution (possible infinitely many). Additionally if you have extra constraints, such as your friend's place and two pizza places lying on a line you need only 2 circles (in $n$ dimensions 2 hyperspheres also). So in the general case you need $n+1$ circles, but it is entirely possible that less are enough in special cases (the minimum being 2, imagine 2 spheres touching at a single point). This problem would be even more interesting on manifolds where the geodesic distance is used for example.

$\endgroup$
  • $\begingroup$ I feel dumb now. I just tried the circle method again with the fake example I made and in that case the circles intersect pretty much perfectly at the point of the house. I guess I had large errors with the real pizza place coordinates and distances, plus two of the real pizza places were nearly in the same direction which resulted in weird overlapping circles. Now I am wondering if probabilities can somehow be applied in some of the cases you were talking about, where there were more than 1 solution. Isn't the probability of the house location higher in sections where 2 circles overlap? $\endgroup$ – Piwwoli Mar 8 at 0:59
  • $\begingroup$ Thank you by the way! I also forgot the very powerful method of simplifying problems when I was trying to figure this out. Should have thought about it with the line and two points like you said and then adapted it to two dimensions. $\endgroup$ – Piwwoli Mar 8 at 1:02
  • $\begingroup$ @Piwwoli Depends on the assumptions regarding the error of your measurements. In case you know the error's probability distribution you can try to predict the 'better' location, that's not as trivial though. I would just go with finding a point that's closest to all 3 circles in case they do not intersect, or the method with using rings rather than circles and then taking the point that's farthest from all edges in the intersection region. $\endgroup$ – lightxbulb Mar 8 at 1:04
  • $\begingroup$ By a ring I mean the region enclosed between the circles with radii $r+\epsilon$ and $r-\epsilon$ and the same center, where $\epsilon \in [0,r]$ is some relatively small value to account for the measurement error. Note that you can pick two different values $\epsilon_1, \epsilon_2$ for the plus and minus, but all of this boils down to the assumptions you make about the error. $\endgroup$ – lightxbulb Mar 8 at 1:09
  • $\begingroup$ Here's something for extra insight. When you say that point $X$ is at a distance (euclidean distance) $r$ from point $C$, where you know $r$ and $C$, then $X$ lies on the hypersphere with center $C$ and radius $r$. That is, the set of all points at a distance $r$ from $C$ forms a hypersphere (in 2d a circle). When you have a constraint such that a point is in two sets at the same time, that means that it is in their intersection. That's why when you ask for a point that's at distances $r_1, r_2, r_3$ away from points $C_1, C_2, C_3$ respectively... $\endgroup$ – lightxbulb Mar 8 at 1:24

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.