Is there a sensible way to sort coordinates?

Question

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.

Answer 1

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.

Answer 2

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.