60

Bit of a strange question but hope this is OK to ask here.

Has anyone heard of a '1-dimensional' projection of the world map - that is mapping all the points on the globe to a single line?

I was thinking of doing such a thing - trying to keep cities that are 'close' on the globe 'close' on the line.

Before I do this, I wondered what the state of the art might be in this area?

Improve this question
4
  • Good idea,but I would like to say that line is '2-dimensional' feature.
    – Vent Lam
    Commented Oct 11, 2011 at 4:02
  • 16
    Lines are 1-dimensional because it only takes one coordinate to locate any point along it. Points are 0-dimensional and polygons are 2-dimensional.
    – blah238
    Commented Oct 11, 2011 at 4:36
  • 5
    the Apple Peel projection: t1.thpservices.com/fotos/thum4/013/881/sfd-362035.jpg, though I've not encountered any ready-to-use algorithms for it... ;-)
    – matt wilkie
    Commented Oct 11, 2011 at 19:02
  • 3
    @Matt That's a cute one. To a good approximation, this projection maps points near (lat,lon)=(f,l) to (Int((90-f)/e),l) where e is the number of "spirals" in the peel. (I'm fudging a little, but this is the gist of it.) The problem is that as e gets large, the points of discontinuity grow dense, implying that it has exactly the opposite of the desired behavior: almost all pairs of points that are close on earth get mapped far from each other.
    – whuber
    Commented Oct 11, 2011 at 19:39

6 Answers 6

Reset to default
52

A general technique for mapping a collection of points (for which distances are given) into a Euclidean space (such as three-space, a plane, or even a line) with minimal distortion of the distances is called Multidimensional Scaling (MDS). There are several algorithms. Solutions are freely available in R and often are supplied with commercial statistics packages.

The largest 20 cities in the US are mapped here with Stata 11's default MDS settings. The ticks denote 100 km intervals.

One-dimensional US

Improve this answer
5
  • brilliant - yes this was exactly what i was planning to do - though I was hoping to use the MDS algorithm called "Stochastic Neighbour Embedding" but yeah same in essence. I see that you did this, already, however. Main thing I think, is that it looks pretty logical/good to me ! I mean interesting, it's own way. Thanks!
    – utunga
    Commented Oct 11, 2011 at 19:53
  • Multidimensional Scaling is 2D stuff!
    – huckfinn
    Commented Feb 3, 2014 at 22:01
  • @huckfinn It can be done in any number of dimensions; 2 is merely a common application. See, inter alia, Buja et al. who provide no limits on the dimension k and whose very first example (Figure 1, left) clearly works in one dimension. Or just look up at my 1D MDS solution!
    – whuber
    Commented Feb 3, 2014 at 22:06
  • Yes that's true, but below 2D IMO it makes it no sense, MDS will be degraded to normal distance measurement and re-projection to the numberbeam. Ordination turns into sortation I'm not shure?
    – huckfinn
    Commented Feb 3, 2014 at 22:18
  • Are you really claiming that the map I present in this answer "makes no sense"? That's going to need considerable explanation on your part, as anyone can plainly see that (1) it does convey useful geographic information and (2) it does not reduce to "normal distance measurement."
    – whuber
    Commented Feb 3, 2014 at 22:48
17

Thanks very much to @whuber for the initial answer. thought I should upload the results of me doing much the same...

For what its worth the particular form of MDS that I used is something called t-SNE (aka 't-distributed Stochastic Neihbor Embedding') to achieve the following images.

Here's a picture of all the cities in order - on the left axis is the actual 1-d location for that city, and the cities arranged in order from top to bottom, left to right across that axis.. color = country cities in order

Here's another picture where I took the line of cities but plotted it on the world map.. I guess bottom line this problem reduces to something pretty close to the traveling sales person problem - but with the difference that its not just an ordering of cities but a mapping of cities to a 1-d line...

path through the world map

If anyone wants the full output data or methodology used here, please message me.

--

EDIT:

In response to @whuber's commment..

Yes you are right when you emphasize local distance (that is that local distances of immediate neighbours should be as close as possible to actual distances on the world map) the MDS problem reduces to the travelling salesman problem. However if you emphasize the optimizing (or matching) of distances over a wider/more moderate range you can get different results. For example here's what the the t-sne algorithm gives when you use a higher value for 'perplexity': enter image description here

Improve this answer
3
  • Thanks for sharing. This really is more akin to traveling salesman: it's not MDS. An MDS solution would have much more distortion but much more of a regular, predictable relationship between the world and the map. As such, your reply constitutes yet another solution to the original problem.
    – whuber
    Commented Nov 23, 2011 at 19:07
  • updated my answer to give another variation, be interested in your views.
    – utunga
    Commented Nov 23, 2011 at 22:30
  • The second is a curious and interesting solution, indeed. It appears your "t-sne" algorithm attempts to visit each point exactly. This is kind of analogous, in the 2D case, to creating a highly accurate local projection around each point and then allowing the projection to break between the points, grievously distorting their distances and orientations while maintaining near-perfect local fidelity. I suppose that could have some specialized use, but in practice one usually permits a little bit of projection error because it allows enough slack to greatly improve the global solution.
    – whuber
    Commented Dec 22, 2011 at 18:46
12

What you can do is cover your 2-d space with a 1-d space-filling curve, such as a Peano curve or Hilbert Curve. Then you map your points onto the nearest point on the curve. Unwrap the curve and you should to a certain extent get a line with nearest cities in space nearest on the line.

It's not perfect (I don't think anything can be), but I've seen it used as a basis for a travelling saleseperson algorithm - the idea being that if you doing your salesperson trip along the line it will be a good approximation to the best solution.

Improve this answer
5
  • 4
    This does work, but be careful: nearest cities one the line will be near in space, but near cities in space will in general not be close to each other on the line (the curves map ℝ->ℝ² continuously, by don't have a continuous inverse).
    – leftaroundabout
    Commented Oct 11, 2011 at 17:51
  • 2
    this answer would benefit from a graphic example of what a Peano/Hilbert Curve looks like (and/or links to definitions)
    – matt wilkie
    Commented Oct 11, 2011 at 18:52
  • 1
    or you could go to wikipedia yourself... its all there, I don't really see the point in repeating wikipedia here too much...
    – Spacedman
    Commented Oct 11, 2011 at 19:06
  • 1
    Well, I think you can repeat it a little bit! How about a link or two and an image?
    – blah238
    Commented Oct 12, 2011 at 0:24
  • For illustration purposes, one can look at Randall Munroe's XKCD map of the Internet, which uses precisely this technique (although in reverse, i.e. mapping a line to a plane)
    – waldyrious
    Commented Dec 9, 2013 at 18:20
9

Strange questions are often the most interesting ones!

If you are looking for a state of the art in the way dimensions are used in cartography, you could start with Bertin's graphics semiology. According to Bertin, a piece of paper (or a ipad surface) has 3 dimensions: The two planar dimensions, plus the value/texture. Graphics semiology provides rules to map information dimensions to these representation dimensions. When the two planar dimensions are the spatial dimensions the graphic is a map, and the third dimension is used for the information to represent.

If you want to make a 1-dimensional map, it means that you choose to restrict not to use one of the paper's dimensions to represent the information you want to (the proximity between cities). Is it really needed to impose such constraint and not make a normal map?

If it is really needed, as said in other answers, it cannot be done! The proximity relation between cities cannot be represented in one dimension. For that, you could:

  • Use a "user centric approach": If the map audience is located somewhere or there is a specific place to focus on, this place may be taken as an origin, and all other cities may be sorted according to their distance to this origin.
  • Sort the cities not only according to their relative distance, but according to other similarity criteria (population, continent, number of cars per inhabitant, etc.). Then, some statistical treatments such as principal components analysis could give a single dimension line the cities could be ranked along.
Improve this answer
2
  • All of the answers here so far are very interesting, and illuminating. The first bullet in this one, pick an origin point and all others are "distance from origin", seems to be the most immediately practical.
    – matt wilkie
    Commented Oct 11, 2011 at 18:58
  • Projection into two dimensions "cannot be done," either, as is well known! BTW, there are loads of applications for 1D projections, such as strip maps for planning trips.
    – whuber
    Commented Oct 11, 2011 at 20:29
7 
trying to keep cities that are 'close' on the globe 'close' on the line

Imagine three cities at the same distance from each other, e.g. at the vertices of an equilateral triangle. How would you represent that on a line? Some information will be lost.

Either you discard one dimension entirely, e.g. projecting all cities on a parallel or on a meridian (the latter would be interesting as we are not used to compare the north/south relative position of cities among different countries), or you select a specific one dimensional measure, e.g. "distance from New York".

The Peano curve suggested by Spacedman is very interesting and would make for an original map, but nearby cities could end up very far on that curve.

Improve this answer
2
  • 5
    ... keep your cities close, and your globes closer ...
    – Thomas
    Commented Oct 11, 2011 at 12:28
  • 1
    +1 Good remarks. However, it's not an either-or proposition: you don't have to project to a line or reduce it to the distance from a basepoint. Nonlinear solutions are available, just as they are used for (the usual) 2D projections. The objective is to minimize some measure of the differences between the projected distances and the actual distances. In this respect the Peano curve will be particularly poor, but variants of it (adapted to pass through all desired points at early stages of its construction) could work--sort of.
    – whuber
    Commented Oct 11, 2011 at 20:27
3

I've never used it, but I think a GeoHash might work for this.

Geohashes offer properties like arbitrary precision and the possibility of gradually removing characters from the end of the code to reduce its size (and gradually lose precision).

As a consequence of the gradual precision degradation, nearby places will often (but not always) present similar prefixes. Conversely, the longer a shared prefix is, the closer the two places are.

Improve this answer
3
  • These hashes tend to work by encoding refined subdivisions of the sphere's surface into words, and thereby are inherently two-dimensional. It's not clear how one would extract a one-dimensional coordinate from them (in any meaningful way).
    – whuber
    Commented Oct 11, 2011 at 18:55
  • @whuber So if I had a list of cities and generated hashes for them by passing their lat/long to geohash.org, then sorted the cities based on the hash, wouldn't the ordering of the cities represent a one-dimensional mapping (regardless of how accurate it is)?
    – Kirk Kuykendall
    Commented Oct 11, 2011 at 19:07
  • 1
    It depends entirely on the hash. A mere ordering isn't one-dimensional, it's just an ordering. In addition, you need a meaningful numerical coordinate. If that also comes out of the hash, then indeed you have a 1D projection, but it likely has terrible properties. The whole point to projections is to ignore the distortions that don't matter for the visualization or analysis and minimize those that do. It is highly unlikely that any hash is going to be useful as a projection for most purposes.
    – whuber
    Commented Oct 11, 2011 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.