I need to estimate the Euclidean distance from a point $x\in {\mathbb R}^m$ to a polyhedron $P\subset {\mathbb R}^m$ in terms of distances from $x$ to the tangent hyperplanes which define $P$. By a polyhedron I mean an intersection of a finite number of closed half-spaces in ${\mathbb R}^m$, say $H_1,\ldots,H_n$. In particular, $P$ can be non-compact. It seems to me there should exist a constant $C>0$ (which depends on $H_1,\ldots,H_n$) such that for any $x$ one has $d(x,P)\leq C\cdot {\rm max} (d(x,\partial H_1),\ldots, d(x,\partial H_n)).$ Here $d(x,Y)$ is the distance from $x$ to a subset $Y$. Any ideas about how to approach a proof?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Is this not a counter example? Take $P = \{ (x,y) \mid y \ge 1, y-\varepsilon x \le 0 \}$. As $\varepsilon \to 0$, $d(0,P)$ can be made arbitrarily large, but the distance from 0 to the two bounding hyperplanes remains $1$ and $0$ respectively. $\endgroup$– Igor KhavkineCommented Feb 8 at 23:57
-
$\begingroup$ The constant C may depend on P. In your example, on the parameter $\varepsilon.$ $\endgroup$– Anton KapustinCommented Feb 9 at 4:39
-
$\begingroup$ @IgorKhavkine Good example, since it's not required to be compact. $\endgroup$– Vlad PatryshevCommented May 10 at 17:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Consider the normal vectors $n_i$ to the planes $\partial H_i$. If they do not span $\mathbb{R}^m$, then they are all orthogonal to a certain vector $e$, and we may choose a hyperplane orthogonal to $e$ and intersect everything with it. Both sides do not change, and the dimension is decreased, so we may just induct on dimension. If they span $\mathbb{R}^m$, the $P$ does not contain a line, thus it has an extreme point $v$ (belonging to $m$ planes with independent normals). The distance even to $v$ alone does not exceed a constant times maximum of distances to these $m$ planes.
answered Feb 8 at 13:40
-
$\begingroup$ Not only that, but also have to walk through all the nodes. $\endgroup$ Commented Feb 8 at 14:03
-
$\begingroup$ @VladPatryshev I do not understand, sorry $\endgroup$ Commented Feb 8 at 15:55
-
$\begingroup$ Yes, but the last statement still needs a proof, see below. $\endgroup$ Commented Feb 8 at 22:41
-
$\begingroup$ The last statement: Choose coordinates so that $v$ is an origin. Then the distance to $v$ does not exceed the sum of absolute values of coordinates, and each coordinate function is a linear combination of the (signed) distances to our $m$ planes with fixed coefficients. $\endgroup$ Commented Feb 8 at 22:57
$\begingroup$
$\endgroup$
1
(Proof provided by P. Etingof): Pick a vertex of P(if there are no vertices, proof is similar). Let us assume that this vertex at the origin. Then $d(x,P)\leq |x|$. Let $v_i$ be the normal unit vectors to the hyperplanes $H_i$ going through the origin. Then $v_i$ span $R^m$. The distances to $H_i$ are $|(x,v_i)|$. We may assume that $v_i$ are a basis (by removing redundant ones). Then $v_i=\sum a_{ij} e_j$ where $A$ is an invertible matrix. So $e_j=\sum b_{ji} v_i$, where B is inverse matrix to A. Thus $x_j=(x,e_j)=\sum b_{ji}(x,v_i).$ So $|x|\leq ||B||*|y|$, where $y_i=(x,v_i).$ Now $|y|\leq m^{1/2}{\rm max} |(x,v_i)|,$ so we can take $C=||B||*m^{1/2}$.
-
$\begingroup$ In general you may need to keep $n\ge m$ hyperplanes $H_i$ at a given vertex, but with any $m$ of the $v_i$ linearly independent. The worst will happen for $x$ along the rays generated by the vertices of the polyhedron $(x,v_i) \le 1$ (choosing the right signs for the $v_i$), that is, where for $m$ of the hyperplanes $(x,v_i) = 1$. So a sharper constant is $C = \max_I \| A_I^{-1} d \|$, where $d=(1,\ldots,1)$ and $A_I$ is the submatrix of $A$ with $m$ rows indexed by $I \subseteq \{1, \ldots, n\}$. One should also of course maximize this $C$ over all vertices of $P$. $\endgroup$ Commented Feb 9 at 11:45