Continuous algorithms (Q1295307): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q406466 |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Ernst-Erich Doberkat / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4002466 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-8641(97)00155-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4213325831 / rank | |||
Normal rank |
Latest revision as of 09:41, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Continuous algorithms |
scientific article |
Statements
Continuous algorithms (English)
0 references
24 June 1999
0 references
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.
0 references
Lipschitz conditions
0 references
sorting
0 references