Let $\lambda$ be Lebesgue measure on [0,1]. For any $x\_{1},\dots,x\_{k}$ in $[0,1]$, define $$A(x\_1,..,x\_k):=\{(y\_1,\dots,y\_k)\in [0,1]^k: \text{there exist intervals }I\_1,\dots,I\_k \text{ in }[0,1]$$ 
$$\text{ such that } x\_i,y\_i\in I\_i \text{ and } \lambda(\cup\_iI\_i)\leq\frac12\}$$ 


My question is: Is it true that there exists a constant $c\in(0,1)$ such that for any $x\_{1},\dots,x\_{k}$ in $[0,1]$ $$\lambda^{\otimes k}(A(x\_1,..,x\_k))\geq c^k$$


(Note that when $x\_1,..,x\_k$ can be covered by a interval of length not larger than 1/2, then $\lambda^{\otimes k}(A(x\_1,..,x\_k))\geq (\frac12)^k$. Thus the question is when $x\_1,..,x\_k$ is quite spread out on $[0,1]$, like for $x\_i=\frac{i}{k+1}$ , is the volume still decay at most exponentially? For $x\_i=\frac{i}{k+1},i=1,2,..,k$, we can construct interval $I\_i=[x\_i,x\_i+\frac{1}{2k}]$, thus $\lambda^{\otimes k}(A(x\_1,..,x\_k))\geq (\frac{1}{2k})^k$. But of course we can construct other intervals and union all situations. )



lower bound volume of a set
Such a constant $c$, not depending on $k$ and $x\_1,\dots,x\_k$, does not exist. 


Indeed, suppose $k\ge2$. Let $x\_i:=(i-1)h$ for $i=0,\dots,k+1$, where $h:=\frac1{k-1}$ -- so that $x\_1=0$ and $x\_k=1$. 


Take any $(y\_1,\dots,y\_k)\in A(x\_1,\dots,x\_k)$. Then there exist intervals $I\_1,\dots,I\_k$ in $[0,1]$ 
such that $x\_i,y\_i\in I\_i$ and $|\cup\_iI\_i|\leq\frac12$; here $|\cdot|$ denotes the Lebesgue measure in any dimensions. Without loss of generality (w.l.o.g.), we can replace here each $I\_j$ by $[x\_j\wedge y\_j,x\_j\vee y\_j]$, so that w.l.o.g. each $I\_j$ is closed. So, for some $m=1,\dots,k$, there exist disjoint nonempty closed subintervals $J\_1,\dots,J\_m$ of $[0,1]$ such that $I\_1\cup\dots\cup I\_k=J\_1\cup\dots\cup J\_m\supseteq\{x\_1,\dots,x\_k\}$. So, w.l.o.g. there are natural $n\_1,\dots,n\_m$ and real $a\_1,b\_1,\dots,a\_m,b\_m$ such that $a\_1=0$, $b\_m=1$, $n\_1<\dots<n\_m=k$, $J\_i=[a\_i,b\_i]$ for all $i=1,\dots,m$, and $x\_{n\_i}\le b\_i<a\_{i+1}\le x\_{n\_i+1}$ for all $i=1,\dots,m-1$. 
So, $\{x\_{n\_{i-1}+1},\dots,x\_{n\_i}\}\subseteq J\_i$ and hence $\{y\_{n\_{i-1}+1},\dots,y\_{n\_i}\}\subseteq J\_i=[a\_i,b\_i]\subseteq[x\_{n\_{i-1}},x\_{n\_i+1}]$ for all $i=1,\dots,m$, with $n\_0:=0$. 
For $i=1,\dots,m$, let $\ell\_i:=n\_i-n\_{i-1}$, so that $\sum\_1^m\ell\_i=k$ and the length of the interval $[x\_{n\_{i-1}},x\_{n\_i+1}]$ is $(\ell\_i+1)h\le2\ell\_i h$. 
So, the Lebesgue measure of the set of all $(y\_1,\dots,y\_k)\in A(x\_1,\dots,x\_k)$ with given $n\_1,\dots,n\_m$ is no greater than $\prod\_1^m(2\ell\_i h)^{\ell\_i}=(2h)^k\prod\_1^m\ell\_i^{\ell\_i}$. 
On the other hand, the cardinality (say $N$) of the set of all $m$-tuples $(n\_1,\dots,n\_m)$ of natural numbers such that $m\in\{1,\dots,k\}$ and $n\_1<\dots<n\_m=k$ is no greater than $2^k$ (consider the indicators of the sets $\{n\_1,\dots,n\_m\}$). 


The crucial observation is that $a\_{i+1}-b\_i\le x\_{n\_i+1}-x\_{n\_i}=h$ for all $i=1,\dots,m-1$ and hence 
$\frac12\le|[0,1]\setminus(J\_1\cup\dots\cup J\_m)|=\sum\_1^{m-1}(a\_{i+1}-b\_i)\le(m-1)h$, so that 
\begin{equation}
 m-1\ge\frac1{2h}=\frac{k-1}2. 
\end{equation}
Therefore and because $\sum\_1^m\ell\_i=k$, for $L:=\max\_i\ell\_i$ we have $k\ge L+(m-1)\ge L+\frac{k-1}2$, whence $L\le\frac{k+1}2\le\frac{3k}4$. 


Thus, 
\begin{equation}
 |A(x\_1,\dots,x\_k)|\le N(2h)^k\max\Big\{\prod\_1^k\ell\_i^{\ell\_i}\colon
 \sum\_1^k\ell\_i=k,0\le\ell\_i\le\tfrac{3k}4\ \forall i\Big\}, 
\end{equation}
with $0^0:=1$. 
Since $\ln(u^u)=u\ln u$ is convex in $u>0$, it follows that $\prod\_1^k\ell\_i^{\ell\_i}$ is Schur-convex in the $\ell\_i$'s, so that for any fixed real $c>0$ 
\begin{equation}
 |A(x\_1,\dots,x\_k)|\le N(2h)^k(\tfrac{3k}4)^{3k/4}
 \le \frac{4^k}{(k-1)^k}\,k^{3k/4}=o(c^k)
\end{equation}
as $k\to\infty$. 


