0

Consider two sets in $\mathbb R^n$, $A = \{x_1,\ldots,x_k\}$ and $B=\{y_1,\ldots, y_m\}$. Suppose that $co(A) \cap co(B)$ are disjoint, where $co(S)$ denotes the convex hull of $S$.

I am interested in doing the following: Pick some point in $A$, say, $x_1$. I want to know whether I can have a supporting hyperplane passing through $x_1$ that separates $co(A)$ and $co(B)$. It is easy to see geometrically that not every point would allow this. Geometrically, it seems that we can have a supporting hyperplane through some point of $A$ or $B$ separating $co(A)$ and $co(B)$ only if they lie on a face facing each other, whatever that means. I want to understand a technical term for this, if there is any.

For example, in the picture below, $H_1$ and $H_2$ separate the rectangle and the triangle and are supported on two extreme points. But we cannot have a hyperplane supported on the rear two points of $A$ that separates $A$ and $B$. Separating two convex sets

Thanks!

avk255
  • 431
  • I think that usually you pick $x_i\in A$ and $y_j\in B$ such that the distance between them is the minimum distance of all possible pairs and then build a hyperplane that goes through the middle of the segment that connects $x_i$ to $y_j$. – Patricio Nov 24 '23 at 09:14
  • Just edited my answer to reflect what I wish to do. – avk255 Nov 24 '23 at 09:46
  • I'm not very clear about what you want. I thought you wanted to construct the hyperplane, but, based on your update, I now believe that you want a name for faces that are close enough. Is that it? – Patricio Nov 24 '23 at 10:49
  • Yes, I want to know if there is a technical term that I can look up to understand which of the extreme points have a supporting hyperplane that can separate $A$ and $B$. As the picture shows, this is possible for $2$ points of $A$ and all the points of $B$ (not shown). – avk255 Nov 24 '23 at 11:08
  • I don't know about a term for it, but the condition would be that $x_1$ lie on a face of $\text{co}(A)$ with $B$ on the opposite side of the plane of that face than $A$. If this is true, then that plane is sufficient for the task. If it is false, then no plane through $x_1$ will separate $A$ and $B$. While this sounds almost the same as your condition, it at least limits you to only having to check a few planes for each point of $A$, not infinitely many. – Paul Sinclair Nov 25 '23 at 17:28

0 Answers0