8

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[0], "and", j[0], "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.

6
  • 1
    Beyond an interesting puzzle, can you describe a real world example of how this would be useful or could be applied? – Sir Swears-a-lot Sep 4 '20 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 '20 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. – rwong Sep 5 '20 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. – TheEnvironmentalist Sep 7 '20 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. – Sir Swears-a-lot Sep 7 '20 at 9:38
14

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.

2
  • 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 – TheEnvironmentalist Sep 3 '20 at 22:58
  • 1
    Your first link is paywalled, but sci-hub gets around it. – J.G. Sep 5 '20 at 14:45
1

Various kinds of 2D queries are supported efficiently by a quadtree (or in 3D by an octtree). The data is grouped adaptively by 2D locality so it's efficient to find neighbors.

As a higher level tool, PostGIS is a PostgreSQL extension that adds Geographical Information Systems (GIS) capabilities to the RDBMS.

The PostGIS project, which is BSD licensed, began back in 2001. It turns our vanilla flavored postgres into a spatial database and includes spatial datatypes (geometry, geography), spatial indexes (r-tree, quad-tree, kd-tree), and spatial functions.

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.