Separation of subsets of $\mathbb{R}^n$ with the graph of a convex function

43 Views Asked by At

Let $A, B \subset \mathbb{R}^n$ be compact and disjoint sets. Assume that there exists a $(n-1)$-dimensional surface $S$ such that separates the $A$ and $B$, i.e. there exists $C \subset \mathbb{R}^n$ such that $\partial C = S$ and $A \subset C $ and $B \subset C^{c}$.

In particular I am interested in the situation when $S$ can be expressed as the graph of a convex function.

Is there a standard name in the literature when this situation happen? I am also looking for sufficient conditions on $A$ and $B$ to ensure this property to hold. For example if they are both convex then I can separate them with an hyperplane and this is of course the graph of a convex function. But it would be nice to find some less trivial sufficient condition.

Any help will be very much appreciated!

1

There are 1 best solutions below

2
On

Assume that $A,\ B$ are compact and disjoint.

And assume that $S$ is convex hypersurface separating $A,\ B$ s.t. $C$ is a convex set and $S=\partial C$. Then we can assume that ${\rm conv}\ A$ is in $C$.

Hence $({\rm conv}\ A)\bigcap B$ has measure $0$.

EXE : So there is a unit vector $v$ s.t. $$({\rm conv}\ \{ a+tv|a\in A,\ t\geq 0\} )\bigcap B$$ has measure $0$ iff there is a convex function $f$ separating $A,\ B$.

Proof : $f: v^\perp \rightarrow \mathbb{R}$ : $f(x)=\infty$ when $x+tv\ \bigcap\ \partial\ {\rm conv}\ A=\emptyset$ for all $t$. And if not, define $f(x)=\min \ \{t| x+tv\in \partial {\rm conv}\ A\}$