On the arrangement of point sets in the unit interval
type: Item
instance of: scholarly article
title: On the arrangement of point sets in the unit interval
zbMATH Open document ID: 1288.11074
author: Peter Kritzer
author: Gerhard Larcher
published in: Manuscripta Mathematica
publication date: 2013-03-18T00:00:00Z
review text: 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). \]
reviewed by: Yukio Ohkubo
Mathematics Subject Classification ID: 11K06
Mathematics Subject Classification ID: 11K38
zbMATH DE Number: 6145957
zbMATH Keywords: point set
zbMATH Keywords: extreme discrepancy
zbMATH Keywords: star discrepancy
MaRDI profile type: Publication
full work available at URL: s00229-012-0547-0
OpenAlex ID: W2100611572
cites work: Q3752472
cites work: Q4063531
cites work: A general rearrangement theorem for sequences
cites work: Point sets and sequences with small discrepancy
cites work: Q4003879
cites work: Random restricted matching and lower bounds for combinatorial optimization
DOI: 10.1007/S00229-012-0547-0
Recommended article: A note on the existence of sequences with small star discrepancy
Recommended article: Some open problems concerning the star-discrepancy
Recommended article: Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory
Recommended article: A note on optimal point distributions in \([0,1)^{s}\)
Recommended article: Exact order of extreme \(L_p\) discrepancy of infinite sequences in arbitrary dimension
Recommended article: Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
Recommended article: Improving a constant in high-dimensional discrepancy estimates
Recommended article: On a class of uniformly distributed sequences of point sets
Recommended article: An algorithm to compute bounds for the star discrepancy
Recommended article: Discrepancy and distance between sets
description: scientific article; zbMATH DE number 6145957