scientific article; zbMATH DE number 3907241
[For the entire collection see Zbl 0563.00013.] The \(\lambda\)-matrix of a configuration \(\{P_ 1,...,P_ n\}\) of points in the Euclidean plane is \(\lambda =(\lambda (i,j))\), where \(\lambda\) (i,j) is the number of points lying to the left of the directed line \(P_ iP_ j.\) The basic theorem of geometric sorting proved in this paper establishes that \(\lambda\) determines, for each pair i,j, the set of these points. This theorem extends also to higher dimensions. The calculation of the \(\lambda\)-matrix can be interpreted as a generalization of the process of sorting points on a line. In this way, it is used to give an efficient algorithm for determining whether two un- numbered configurations have the same order type; thus, it can be applied to pattern recognition and classification and, in higher dimensions, to problems in stereo-chemistry and cluster analysis. A more detailed version of this paper is [the authors, SIAM J. Comput. 12, 484-507 (1983; Zbl 0525.68038)].
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3684737)