Multidimensional Sorting
Jacob Eli Goodman, Richard M. Pollack · SIAM Journal on Computing · 1983
We introduce a process called geometric sorting, which can be applied to an arbitrary configuration of points in d space, and which encodes in compact form the order properties of the configuration, just as the arrangement of a set of numbers in size place encodes its order properties. We give an algorithm for carrying out this sorting procedure in time $O(n^d \log n)$, which generalizes the optimum sorting time of $O(n\log n)$ for the linear case; In addition, we give an efficient algorithm for determining whether two randomly numbered configurations in $\mathbb{R}^d $ have the same order type, using a distinguished family of orderings of each. Finally, we indicate how this new concept of sorting can be applied to problems in pattern recognition, stereochemistry, and cluster analysis.