Continuous algorithms
type: Item
instance of: scholarly article
title: Continuous algorithms
zbMATH Open document ID: 0920.54010
DOI: 10.1016/S0166-8641(97)00155-7
author: Michael D. Rice
published in: Topology and its Applications
publication date: 1999-06-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 54C05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 54C35
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 1308003
zbMATH Keywords: Lipschitz conditions
zbMATH Keywords: sorting
reviewed by: Ernst-Erich Doberkat
MaRDI profile type: Publication
cites work: Q5585020
cites work: Q4002466
full work available at URL: s0166-8641(97)00155-7
OpenAlex ID: W4213325831
description: scientific article; zbMATH DE number 1308003