Block partitions: an extended view (Q722349): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2671268121 / rank | |||
Normal rank |
Revision as of 20:17, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Block partitions: an extended view |
scientific article |
Statements
Block partitions: an extended view (English)
0 references
23 July 2018
0 references
A sequence $A_0,A_1,\dots,A_n$ of closed sets in $\mathbb{R}^d$ is called a grid-like sequence if i) $A_0=\{0\}$ and $A_n=\{s\}$ for a given $s\in\mathbb{R}^d$, and ii) for all $a\in\mathbb{R}^d$ the unit balls $a+B^d$ have an element in common with the sets $A_1,\dots,A_{n-1}$. Here, $B^d$ is the Euclidean ball of radius 1 centered at the origin.\par A transversal $T$ of such a sequence is a collection of points $a_i\in A_i$, $0\leq i\leq n$. The diameter $D(T; A_0,\dots, A_n)$ of a transversal is the maximal distance among the points $z_i=a_i-a_{i-1}$, $1\leq i\leq n$, and the goal is to determine a transversal such that the diameter is as small as possible. Moreover, let $D_d^\star$ be the maximum of all minimal diameters of transversals among grid-like sequences in $\mathbb{R}^d$. \par As shown by the authors, one can easily obtain an upper bound of $D_d^\star\leq 4$, and they state the lower bound $D_2^\star\geq \sqrt{2}$. Due to the technical complexity of this proof, they just present the proof of the weaker lower bound of $\sim 2.071$. \par In the case $d=1$, the balls $a+B^1$ can be replaced by the half-balls (intervals) $[a,a+1]$, and then the above transversal problem is an equivalent rephrasing of a problem on block partitions studied in \textit{I. Bárány} and \textit{V. S. Grinberg} [Isr. J. Math. 206, 155--164 (2015; Zbl 1315.26017)].
0 references
sequence
0 references
block partition
0 references
transversal
0 references