Bounding distance to an intersection of polyhedra

Question

Let $P$ and $Q$ be polyhedra in ${\mathbb R}^m$ with a non-empty intersection. I believe there should exist a constant $C_{PQ}>0$ such that for any point $x\in {\mathbb R}^m$ the following inequality holds: $$d(x,P\cap Q)\leq C_{PQ}\cdot {\rm max} ( d(x,P),d(x,Q)).$$ Here $d(x,Y)$ denotes the Euclidean distance between $x$ and a subset $Y\subset {\mathbb R}^m$. Any suggestions about how to prove this? (A related question: Bounding distance to a polyhedron)

Answer 1

Let $\langle \cdot,\cdot\rangle$ denote an inner product. The polyhedra $P,Q$ may be unbounded (as in the previous cited question).

Lemma. Let $\mathcal{C}_1,\mathcal{C}_2$ be two closed convex cones in $\mathbb{R}^n$ (with the vertex 0), denote by $\mathcal{C}_0:=\mathcal{C}_1\cap \mathcal{C}_2$ their intersection, and by $K=\mathcal{C}_0^\circ=\{k\in \mathbb{R}^m:\langle k,x \rangle\leqslant 0 \,\text{for all}\, x\in \mathcal{C}_0\}$ its polar cone. Then there exists a constant $c_0>0$ depending only on $\mathcal{C}_1,\mathcal{C}_2$ such that $\|x\| \leqslant c_0\max(d(x,\mathcal{C}_1),d(x,\mathcal{C}_2))$ for all $x\in K$.

Proof. By homogeneity, we may assume $\|x\|=1$. Since $K$ is closed, the set $K_1:=\{x\in K:\|x\|=1\}$ is compact, and the function $f\colon x\to \max(d(x,\mathcal{C}_1),d(x,\mathcal{C}_2))$ is continuous, it suffices to prove that $f$ is strictly positive on $K_1$. This is clear: if $f(x)=0$ and $x\in K_1$, then $x\in \mathcal{C}_1$ and $x\in \mathcal{C}_2$, thus $x\in \mathcal{C}_0$, and by definition of $K$ we get $1=\|x\|^2=\langle x,x\rangle \leqslant 0$. A contradiction.

Now to your question. Let $P=\cap_{i=1}^{n_p} P_i$, $Q=\cap_{j=1}^{n_q} Q_j$ where $P_i,Q_j$ are half spaces, and $\alpha_i,\beta_j$ correspondingly their boundaries (affine hyperplanes). Let $y$ denote the point of $P\cap Q$ closest to $x$. Since there are only finitely many possibilities, we may assume that $x$ belongs to, say, $\alpha_1\ldots,\alpha_k$ and $\beta_1,\ldots,\beta_r$ and does not belong to other $\alpha$'s and $\beta$'s. Denote $\mathcal{C}_1=-y+\cap_{i=1}^k P_i$, $\mathcal{C}_2=-y+\cap_{i=1}^r Q_i$. These are closed (polyhderal) cones with vertex 0, and they do not depend on the point $y\in \cap_{i=1}^k\alpha_i\cap \cap_{j=1}^r\beta_j$. Denote $\mathcal{C}_0=\mathcal{C}_1\cap \mathcal{C}_2$, $K=\mathcal{C}_0^\circ$. I claim that $x-y\in K$. Indeed, assume that $z\in \mathcal{C}_0$ and $\langle x-y,z\rangle>0$. Choose very small $t>0$ and look at a point $y_t:=y+tz$. It belongs to $P\cap Q$: indeed, for $i>k$ or $j>r$ the inclusions $y_t\in P_i$, $y_t\in Q_j$ follow from $t$ being very small; for $i\leqslant k$ and $j\leqslant r$ it follows from $t>0$ and $y+z\in P_i$, $y+z\in Q_j$. But $\|x-y_t\|^2=\|(x-y)-tz\|^2=\|x-y\|^2-2t\langle x-y,z\rangle+t^2\|z\|^2$ which is strictly less than $\|x-y\|^2$ for small enough $t$. It remains to apply Lemma and note that $d(x,P)\geqslant d(x,\cap_{i=1}^k P_i)=d(x-y,\mathcal{C}_1)$, and the same for $Q$.