Continuous algorithms (Q1295307): Difference between revisions

The paper deals with sorting and order statistics in Euclidean \(n\)-space from a topological point of view, the topology considered being the usual one. A typical example of the things discussed is given by the following: a map \(g:\mathbb{R}^n \to\mathbb{R}^n\) is said to preserve monotonicity iff for each nondecreasing function \(f:\mathbb{R} \to\mathbb{R}\) the relation \(f^*\circ g=g\circ f^*\) holds, \(f^*\) mapping \((x_1, \dots, x_n)\) to \((f(x_1), \dots, f(x_n))\). An order statistics \(h\) on a subset \(U\) of \(\mathbb{R}^n\) is a map \(h:U\to \mathbb{R}\) such that for any \(x\in U\) there exists an index \(i(x)\) with \(1\leq i(x)\leq n\) and \(h(x)= x_{i(x)}\). Then Theorem 2 states that \(g:\mathbb{R}^n\to\mathbb{R}^n\) preserves monotonicity iff \(\pi_i \circ g\) is a continuous order statistics for each projection \(\pi_i\). The second part of this paper relates properties to determining sets. E.g., a subset \(F\subseteq\mathbb{R}^n\) determines sorting iff, whenever \(g| F=\text{Sort}| F\) holds for an in-place map \(g:\mathbb{R}^n \to \mathbb{R}^n\), then \(g\) equals Sort (an in-place map permutes simply its inputs). The author shows among other properties that if each element of \(F\) has distinct components, and if \(F\) determines sorting, then \(F\) must contain at least (\((2^n -2)/(n-1)\) elements. The paper is interesting, albeit a bit unusual in its scope, it is written in a clear style, and the proofs are clever but not overly complicated.