Multidimensional Sorting
Multidimensional Sorting
复制标题
多维排序
DOI：
10.1137/0212032
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
R. Pollack
中科院分区：
文献类型：
--
作者：
J. Goodman;R. Pollack
我们引入了一个称为几何排序的过程，它可以应用于空间中任意点的构型，并以紧致形式编码构型的顺序属性，就像一组数字在大小位置上的排列编码其顺序属性一样。给出了一种实时排序算法，推广了线性情况下的最优排序时间；此外，我们给出了一种有效的算法来确定两个随机编号的结构是否具有相同的顺序类型，使用每个结构的不同的排序族。最后，我们指出了如何将这种新的排序概念应用于模式识别、立体化学和聚类分析中的问题。
We introduce a process called geometric sorting, which can be applied to an arbitrary configuration of points indspace, 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, which generalizes the optimum sorting time offor the linear case; In addition, we give an efficient algorithm for determining whether two randomly numbered configurations inhave 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.