Algorithms Math

Reachability on arbitrary maps

The other day I had an idea. What if you took a map of some country, and from each coordinate computed the time it took to any other coordinate. The basic assumptions are that you can drive on road by car from parking lot to parking lot, and from parking lot to another point you can get only by foot. You can also add trains, and airplanes, each having less routes, but are actually faster. So for example, traveling from city A’s center to city B’s center is quite fast, but traveling from city A’s center to some point near the road from A to B will take some time.

This is a bit similar to computations done by game AI’s to determine how to get from point A to point B on a game board.

Now let us assume assume we want to draw the resulting graph on some kind of a 3D map, where the distance of each point from other points is determined by the time it takes to reach from that point to the others. Actually, it might not always be possible to plot this graph on a 3D map as a friend pointed to me, as 3 neighboring points already lock our point in space. But let us say that you can plot this 3D map. A’s center and B’s center will be near each other, a bit like a paper folding – which is incidentally the most common depiction of ‘science fiction wormholes’ explanations to laymen. It was pretty nice to try and visualize this kind of map. It is also interesting to think what is the least number of dimensions required to plot a given map.

Although I couldn’t come up with ideas about how this kind of visualization might be useful, it was still fun to to think of.

2 replies on “Reachability on arbitrary maps”

you could draw a good approximation of the graph you search by creating some sort of gravity map. For every pair of points you define a certain strength of attraction between those points and a certain optimal distance. After that, you throw your elements on a grid in three dimensional space. For each iteration, you can define the energy between 2 points to be the distance from the optimal distance multiplied with the strength of attraction. If you sum up the energy for all points, you get the maximum energy.
This maximum energy has to be minimized by given algorithms.

You whould not get the exact image, but you could get a good approximation of that thing in three dimensions.


Interesting idea. Although I am in no position to even approach solving it, I quite like the “least number of dimensions required to plot a given map” problem. Meanwhile, I think I have a fitting name for your concept : “isochronic tri-dimensional anamorphose”. Sounds like a mouthful, but that’s the best I came with…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.