You Must Now Answer Math... QuESTions!!!

[Gnome Alone]

Hi playgroundlings - So, I work at a library and recently I had to go to another branch for some training (it was on what to do if some lunatic comes in shooting, so hey, barrel of laughs there) and in the process of getting reimbursed for the travel (if memory serves, it was a whopping three point something bucks) I encountered a wee Excel spreadsheet that listed every branch and then the distance between every branch (e.g., branch F is 5 miles from branch Y and branch Q is 11 miles from branch N, etc.) and with curiosity most powerful and idle, I was wondering if any of you dudes that, like, know things about stuff could tell me if there would be a way to take in the said data of relational distance and thus plot out a map of the locations, without knowing anything about the geography other than the distances between branches, and if so, what this method would be called. My guess is that it'd be something to do with algorithms, but about this, I'm an idiot, so I was mainly asking out of an itchy, burning curiosity.

[Juggling Goth]

I cannot answer your maths question (puzzles like that I do entirely by trial and error, or ask my girlfriend who loves the stuff), but thought I'd offer some fellow-library-staff solidarity in a world where this is a thing:


So, I work at a library and recently I had to go to another branch for some training (it was on what to do if some lunatic comes in shooting, so hey, barrel of laughs there)

I jumped ship from public to academic libraries a few years ago. They're marginally less frightening.

[TuggyNE]

Well, this is basically an application of trigonometry. I don't know the name of the algorithm, but here's how I'd do it:

Pick one branch randomly from the list
Pick another random branch that has a listed distance from the first, and place it at that distance; all you know is that it's within a circle, so just randomly pick some direction to orient it
Pick another branch that has distances to the first two; you can now pin its location down to one of two points on the map
Pick a fourth branch with distances to the other three, and you should now be able to figure out which side the third branch is on
Continue adding branches, selecting at each iteration from branches that have at least three distances to branches already in the diagram

[Teddy]

Hi playgroundlings - So, I work at a library and recently I had to go to another branch for some training (it was on what to do if some lunatic comes in shooting, so hey, barrel of laughs there) and in the process of getting reimbursed for the travel (if memory serves, it was a whopping three point something bucks) I encountered a wee Excel spreadsheet that listed every branch and then the distance between every branch (e.g., branch F is 5 miles from branch Y and branch Q is 11 miles from branch N, etc.) and with curiosity most powerful and idle, I was wondering if any of you dudes that, like, know things about stuff could tell me if there would be a way to take in the said data of relational distance and thus plot out a map of the locations, without knowing anything about the geography other than the distances between branches, and if so, what this method would be called. My guess is that it'd be something to do with algorithms, but about this, I'm an idiot, so I was mainly asking out of an itchy, burning curiosity.

Assuming that the distances are bird's flight and not all too rounded, you can do this with just a paper, a pencil and a ruler (and perhaps a compass for convenience's sake):

Draw a dot representing the first branch
Draw a dot representing the second branch at the correct distance from the first (using, say, 2 miles per centimetre (5 per inch), or another scale which fits your paper).
Draw circles around the first two branches with the radius representing the third branch's distance from them. Pick one intersection, and put the third branch there. If the third branch ended up on a perfect line together with the other two, repeat this step for the following branches until one doesn't. You should now have three dots creating a triangle (I'll call the third dot in the triangle the "third branch" below).
For each other branch, draw circles around the first, second and third branch and put them down where all three circles intersect(-ish).


You will now have a map of the locations of the different branches in relation to eachother, or a mirror thereof (depending on which intersection you picked for the third). It doesn't say anything about which direction on the paper is north, though...

EDIT:
Should've checked for ninjas before posting... :smallwink:

[rs2excelsior]

And as far as what the method would be called, I believe it is triangulation, or some variation thereof.

[Taffimai]

Because you only know the distance between cities and not their North/South and East/West orientation from one another, you will end up with two possible maps that are each other's mirror image with no way to determine which one is correct until you go out and observe reality somehow.

Apart from that, you will also have no way of knowing which part of your map is "up" (North), but that is a simple matter of rotation.

[Flickerdart]

Because you only know the distance between cities and not their North/South and East/West orientation from one another, you will end up with two possible maps that are each other's mirror image with no way to determine which one is correct until you go out and observe reality somehow.

Apart from that, you will also have no way of knowing which part of your map is "up" (North), but that is a simple matter of rotation.
It's likely that some branches will have names that betray their orientation. For instance, in Toronto, the North York Central library is, like its name suggests, in the north of the city.

[Brother Oni]

Because you only know the distance between cities and not their North/South and East/West orientation from one another, you will end up with two possible maps that are each other's mirror image with no way to determine which one is correct until you go out and observe reality somehow.


This is also making the assumption that you have a full set of data.

It's not particularly useful if you know A-B is 10 miles and B-C is 10 miles but unknown to you, A-C is only 1 mile.
As Teddy said, it also depends on these distances being as the crow flies, as you can get oddities where A-D is 5 miles, but D-A is 7 since there's a tortuous one way system inbetween.

That said, normally these sort of admin expenses charts are very detailed and list the 'official' distances between every branch in a table.
A particularly flashy version may have macros or validated data entry cells that can look up distances for you if you type in the branch names.

[Gnome Alone]

Thanks for the replies, everyone. Look at you guys, all like, knowing stuff, it's awesome. I now understand something better than I did before, and what more can you ask, really?


I jumped ship from public to academic libraries a few years ago. They're marginally less frightening.

Hmm, thanks, that's good to know. I don't know exactly where I'll end up but that is worth checking out; I live in Sacramento, capital of the State of California, and might also end up working at the state library or somesuch eventually.


Because you only know the distance between cities and not their North/South and East/West orientation from one another, you will end up with two possible maps that are each other's mirror image with no way to determine which one is correct until you go out and observe reality somehow.

Apart from that, you will also have no way of knowing which part of your map is "up" (North), but that is a simple matter of rotation.

I figured there would be something like this, the mirror image thing. That is fascinating.

[AttilaTheGeek]

In fact, triangulation is how GPS satellites find your position.

Think of it like this: If you know the mystery library is a certain distance, call that distance x, from a point A (say, another library), then the mystery library is somewhere on a circle with radius x centered on A. It has to be, because that circle is the set of points that fulfill your condition of "the distance to point A is x". Then, you need another point (another library, perhaps), call it B, and its distance to your mystery library, y. You know that the library is also on a circle with radius y centered on B, because it is a distance y from B. Therefore, since you know the point is on the first circle and on the second, then it must be on an intersection between the two circles. If the point is on a line between A and B, then there is only one point where the circles meet, so the point must be there. However, it's much more likely that the point is not on that line, in which case the two circles will overlap like a venn diagram. If that's the case, there are two possible places where the mystery point could be, and you need its distance to a third point, C, to find out which one it is. And that's how you triangulate a point's location by knowing its distance to three other points!

[Drumbum42]

This reminds me of the stuff I did in my algorithms class in College. (I was a computer science major) I made programs that made networks made from either points (x,y coordinates) or distances between points, like what you have. It got interesting when we had to find the fastest way to traverse our new network.

So, in the context of what you have, what is the fastest way you could visit every library given the distances provided. In short it's called the Traveling Salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem), and it's a type of problem that computers have a hard time solving. In order to find the FASTEST way, it has to check EVERY possible combination of libraries, it could take 5 seconds, or 5 lifetimes of the universe depending on how many libraries there are.

I always laugh when the estimated completion time of a computer program is measured in life times of the universe. "Oh your 4GHz computer if fast? Run this program and tell me if it finishes before the sun explodes."

[IthilanorStPete]

In fact, triangulation is how GPS satellites find your position.

Think of it like this: If you know the mystery library is a certain distance, call that distance x, from a point A (say, another library), then the mystery library is somewhere on a circle with radius x centered on A. It has to be, because that circle is the set of points that fulfill your condition of "the distance to point A is x". Then, you need another point (another library, perhaps), call it B, and its distance to your mystery library, y. You know that the library is also on a circle with radius y centered on B, because it is a distance y from B. Therefore, since you know the point is on the first circle and on the second, then it must be on an intersection between the two circles. If the point is on a line between A and B, then there is only one point where the circles meet, so the point must be there. However, it's much more likely that the point is not on that line, in which case the two circles will overlap like a venn diagram. If that's the case, there are two possible places where the mystery point could be, and you need its distance to a third point, C, to find out which one it is. And that's how you triangulate a point's location by knowing its distance to three other points!

Slight nitpick - because GPS is working in three dimensions, four distances are needed. If the satellites are at locations A, B, C, and D, and you're at location X, then:
-knowing the distance AX constrains X to be on a sphere, centered on A
-knowing BX as well constrains X to the intersection of two spheres, which is normally a circle
-knowing CX constrains X to one of two points on that circle
-knowing DX indicates which of those points is X.

[Teddy]

So, in the context of what you have, what is the fastest way you could visit every library given the distances provided. In short it's called the Traveling Salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem), and it's a type of problem that computers have a hard time solving. In order to find the FASTEST way, it has to check EVERY possible combination of libraries, it could take 5 seconds, or 5 lifetimes of the universe depending on how many libraries there are.

I always laugh when the estimated completion time of a computer program is measured in life times of the universe. "Oh your 4GHz computer if fast? Run this program and tell me if it finishes before the sun explodes."

Well, that's not entirely true, there are many really good estimation algortithms out there which can find the fastest route faster than in quadratic time. They're even faster if you give them a fast enough criterium instead.


Slight nitpick - because GPS is working in three dimensions, four distances are needed. If the satellites are at locations A, B, C, and D, and you're at location X, then:
-knowing the distance AX constrains X to be on a sphere, centered on A
-knowing BX as well constrains X to the intersection of two spheres, which is normally a circle
-knowing CX constrains X to one of two points on that circle
-knowing DX indicates which of those points is X.

Given, since GPS never was created for space navigation, you can safely assume that you'll always be at the point inside of orbit, meaning that only 3 satellites are necessary. Furthermore, since your north-south and west-east coordinates won't change no matter how high above Earth you are, this is only a problem to start with for height-sensitive applications.

[IthilanorStPete]

Given, since GPS never was created for space navigation, you can safely assume that you'll always be at the point inside of orbit, meaning that only 3 satellites are necessary. Furthermore, since your north-south and west-east coordinates won't change no matter how high above Earth you are, this is only a problem to start with for height-sensitive applications.

That requires having more information, though, which somewhat defeats the point of GPS. In cases of ships or planes where altitude is easily known, that can simplify things, but normally it's just easier to solve the navigation equations with four distances.

[Drumbum42]

Well, that's not entirely true, there are many really good estimation algortithms out there which can find the fastest route faster than in quadratic time. They're even faster if you give them a fast enough criterium instead.

Well, an estimation can't guarantee the FASTEST path, only an acceptably good one. To get a THE fastest answer you have to check all of them to be 100% sure. But that was the point of my class, get the best answer, +/-5%. And that is much easier.


That requires having more information, though, which somewhat defeats the point of GPS. In cases of ships or planes where altitude is easily known, that can simplify things, but normally it's just easier to solve the navigation equations with four distances.

And even with cars too. Taking a tunnel under a mountain vs a path over it will mess with 3 satellites unless the topology is really well known.