On the arrangement of point sets in the unit interval (Q1942247): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00229-012-0547-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2100611572 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3752472 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4063531 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A general rearrangement theorem for sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Point sets and sequences with small discrepancy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4003879 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random restricted matching and lower bounds for combinatorial optimization / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:34, 6 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the arrangement of point sets in the unit interval |
scientific article |
Statements
On the arrangement of point sets in the unit interval (English)
0 references
18 March 2013
0 references
Let \(X=(\mathbf{x}_n)_{n=1}^M\) and \(Y=(\mathbf{y}_n)_{n=1}^N\) be two point sets in \([0,1)^s\) with \(1\leq M\leq N\). The following quantity is defined \[ \|X\rightarrow Y\|:=\min_{\substack{ f:X\to Y\\ f\,\text{injective}}}\sum_{n=1}^M\|f(x_n)-x_n\|_2, \] where \(\|\cdot\|\) denotes the usual euclidean norm. \textit{S. Steinerberger} [J. Comb. Optim. 24, No. 3, 280--298 (2012; Zbl 1282.90156)] showed \[ \|X\rightarrow Y\|\leq \sqrt{s}\left(D_N(Y)+\frac{M}{N}\right)^{1/s}M, \] where \(D_N(Y)\) is the extreme discrepancy of \(Y\). The authors improve on the result of Steinerberger in dimension one. First they give the following result on arrangement of a finite point set. For \(Y=(y_n)_{n=1}^N\subset [0,1)\) with the star discrepancy \(D^*_N(Y)\) there exists a permutation \(\pi\) of the set \(\{1,\dots, N\}\) such that \[ D^*_M(y_{\pi(1)},\dots,y_{\pi(M)})\leq \frac{\log M}{M\log 2}+\frac{1}{M}-\frac{1}{2N}+D^*_N(Y) \] for \(1\leq M\leq N\). Finally, the authors obtain the following result in dimension one \[ \|X\rightarrow Y\|\leq 2\frac{M}{N}+\frac{M^2}{N}D_M(X)+MD_N(Y). \] Moreover, they show that if \(|x_n-x_k|>1/N\) for \(n, k\in\{1,\dots, M\}, n\neq k\), then \[ \|X\rightarrow Y\|\leq 3\frac{M}{N}+MD_N(Y). \]
0 references
point set
0 references
extreme discrepancy
0 references
star discrepancy
0 references