# Is there a sensible way to sort coordinates?

Sorting is generally used to solve problems where distance between elements matters. A sorted list/array has the convenient property that the smaller the difference between the indices of any two elements, the smaller the difference between the values of the elements.*

When working with lists of coordinates or similar values with more than one dimension, is there an arrangement of the list that has similar properties (for Euclidean distance) to those of a sort in one dimension?

Edited (twice) to add more details:

To be clear, a sorted list `[X, Y, Z]` has the property that the distance between `X` and `Z` cannot be less than that between `Y` and `Z` and that between `Y` and `X`, otherwise the list wouldn't qualify as sorted.

For example, let's say I have the following unsorted list of `(name, X, Y)` coordinates, with the names just in there for convenience:

``````[("A", 58, 45), ("B", 7, 4), ("C", 44, 88), ("D", 60, 100), ("E", 76, 44)]
``````

A simple Python script tells me the Euclidean distances between every pair of elements:

``````import itertools
import math

coords = [("A", 58, 45),
("B", 7, 4),
("C", 44, 88),
("D", 60, 100),
("E", 76, 44)
]

def dist(coord1, coord2) -> int:
name1, x1, y1 = coord1
name2, x2, y2 = coord2
return round(math.sqrt((x1 - y1)**2 + (x2 - y2)**2), 2)

for (i, j) in itertools.combinations(coords, 2):
print("Distance between", i, "and", j, "is", dist(i, j))
``````

With the results:

``````Distance between A and B is 13.34    // Closest two elements
Distance between A and C is 45.88
Distance between A and D is 42.06
Distance between A and E is 34.54    // Third closest elements
Distance between B and C is 44.1
Distance between B and D is 40.11
Distance between B and E is 32.14    // Second closest elements
Distance between C and D is 59.46
Distance between C and E is 54.41
Distance between D and E is 51.22
``````

I've been trying to work out on paper how to arrange these elements such that the rank-distance property of sorting is preserved. So far I've worked out that because `A` and `B` are the two elements with the least Euclidean distance between them, they need to be adjacent post-sort. The pair of elements with the second smallest Euclidean distance is `B` and `E`, so `B` and `E` should be adjacent. The only possible arrangements of `A`, `B`, and `E` with both these adjacencies are `[A, B, E]`, and `[E, B, A]`. Beyond trial and error however, I can't justify whether this property is always satisfiable.

* Technically, the smaller the difference between the indices of any two elements, the smaller the rank of the difference between the values of the elements. For example, in the list `[1, 5, 6, 8]`, `5` has an index closer to that of `1` than to that of `8`, but 5 as a number is closer to 8 than it is to 1.

• Beyond an interesting puzzle, can you describe a real world example of how this would be useful or could be applied? Sep 4, 2020 at 22:37
• This seems similar to the Traveling Salesman Problem, although in that case you are given just the distance between the points, rather their coordinates.
– bdsl
Sep 5, 2020 at 17:24
• Random Projection is a technique that may be useful for this purpose. It is an example of dimensionality reduction which Michael Borgwardt has covered in his answer. Sep 5, 2020 at 20:54
• @SirSwears-a-lot Finding the closest cafes/restaurants/petrol to your car route, finding antipodal points on spheres and higher-dimensional shapes. Efficiently (`O(N)` after doing the multidimensional sort) figuring out who should go for which chair in music chairs. Actually lots and lots of mapping problems. Figuring out which servers in a data center should talk to which others for splitting work across nodes. Basically this is just a more general notion of sorting. Off the top of my head, this would be especially useful in navigation, self-driving cars, simulated worlds, graphics and so on. Sep 7, 2020 at 2:33
• @TheEnvironmentalist i understand the goal but i dont see why storing every possible combination is useful. Im a DBA and have written a number of spatial queries, such as "nearest neighbour" and they generally perform well. If there was a massive number of points you could limit the available set by box bounding or filtering before looking for optimal pair. TLDR: Storing data means maintaining it. Many to many relationships are even more difficult. My advice is "dont". Calculate it on the fly instead. Sep 7, 2020 at 9:38

the smaller the difference between the indices of any two elements, the smaller the difference between the values of the elements.

When working with lists of coordinates or similar values with more than one dimension, is there an arrangement of the list that has similar properties to those of a sort in one dimension?

What you want is called Distance‐preserving dimensionality reduction.

A Z-Order Curve has this property - but only approximately, i.e. the smaller the difference between the indices of any two elements, the higher the likelihood that the values are close to each other. But there are outliers.

And that's the best you can do. An ordering of multidimensional coordinates in a single dimension that strictly preserves the multidimensional distance metric is impossible. Simply consider the case of 3 points that form an equilateral triangle. However you sort them in one dimension, two of them will have a distance twice as big from each other as from the third (middle) one.

• I think this is exactly what I'm looking for, though the part at the end is slightly different from the sorting property. Unless there exist constraints involving other points in the list that require a specific ordering, the three points that make up an equilateral triangle could be sorted in any order, just as in a one-dimensional sort, the named elements `[("A", 1), ("B", 1), ("C", 1)]` could validly be arranged in any order by traditional (one-dimensional) sorting algorithms. `[A, B, C]`, `[A, C, B]`, `[B, A, C]`, etc. all preserve the sorting properties Sep 3, 2020 at 22:58