Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $C$ be a compact convex subset of Euclidean space. Recall that $x\in C$ is an exposed point of $C$ if there is a plane $P$ such that $P\cap C = \{x\}$. It is obvious that exposed points are extreme. To see that they are not equivalent, draw two parallel lines and put half circles on each end.

Straszewicz's theorem asserts that the exposed points are dense in the extreme points. In particular, the closed convex hull of the exposed points of $C$ is equal to $C$.

I would like a quantitative version. Most likely there is a well-known quantitative version, but I am googling the wrong words.

Here is a proposed version:

Call a point $x\in C$ an $\epsilon$-exposed point of $C$ if there is a ball $B$ of radius $r\leq \epsilon^{-1}$ such that $C \subseteq B$ and $C \cap \partial B = \{ x \}$. Let $C_\epsilon$ be the closed convex hull of the $\epsilon$-exposed points of $C$. Then the Hausdorff distance between the sets $C$ and $C_\epsilon$ is at most $A \epsilon$ (or something else, but I'd like it explicit in $\epsilon$) where $A>0$ depends on the dimension and the diameter of $C$.

(I am not sure this is very difficult and I am not sure this is very easy. Just wondering if something like this already exists before I am forced to spend time proving it...)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

$\let\eps\epsilon$ $\def\conv{\mathop{\rm conv}}$ A set is called $R$-strictly convex if it is an intersection of balls of radius $R$. Denote by ${\mathop{\rm conv}}_R C$ the $R$-strict convex hull of $C$, that is --- the intersection of all balls with radius $R$ that contain $C$ (we assume that the diameter of $C$ does not exceed $R$).

The result you need is a consequence of the following

Lemma. Let $B$ be a convex compact set of diameter $\leq D$ an Euclidean space. Then for all sufficiently large $r$ the Hausdorff distance between $B$ and ${\mathop{\rm conv}}_r B$ does not exceed $A/r$, where $A$ depends only on $D$ (it even does not depend on the dimension!).

1. Let us show that the Lemma implies the statement under the question. Consider $r$ which is a bit smaller than $\eps^{-1}$ and let $B_\eps=\conv_rC_\eps$. We claim that $C\subseteq B_\eps$ (hence by Lemma the distance between $C_\eps$ and $C$ is at most $A/r$).

Actually, assume that $C\not\subseteq B_\eps$. Then $\conv_r C\neq B_\eps$, which means that $\partial \conv_r C$ contains some point $c\in C$ which is not in $B_\eps$. This point lies on the boundary of some ball of radius $r$ containing $C$; if we scale this ball at $c$ so that its raduius reaches $\eps^{-1}$ we will see that $c$ is an $\eps$-exposed point; this contradicts to the definition of $B_\eps$.

2. It remains to prove the Lemma. In fact, we show that if $d(x,B)>r-\sqrt{r^2-D^2}=D^2/2r+o(1/r)$ then $x\notin \conv_r B$. Consider the point $y\in B$ such that $d(x,B)=\|x-y\|$, and take the hyperplane $p$ passing through $y$ and perpendicular to $x-y$. Then $p$ is a supporting hyperplane for $B$; that means that $B$ is contained in the intersection of the halfspace $P$ bounded by $p$ and the ball $K$ with center $y$ and radius $D$. Now take the ball $L$ of radius $r$ whose center $o$ lies on the line defined by $x,y$ inside $P$, and whose boundary contains $\partial K\cap p$. Then $L\supset K\cap P\supset B$. On the other hand, $\|o-y\|=\sqrt{r^2-D^2}$, hence $\|o-x\|>r$, and $x\notin L$. Thus $x\notin \conv_r B$, as desired.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.