How Intertwined are Two Sets of Points? Given two sets of points on the plane, of potentially different cardinalities:
$\mathcal{X}=\left\{\mathbf{x}_1, \dots, \mathbf{x}_{|\mathcal{X}|}\right\}$,
$\mathcal{Y}=\left\{\mathbf{y}_1, \dots, \mathbf{y}_{|\mathcal{Y}|}\right\}$,
what is a good measure of how "intertwined" the two sets are?
The measure should be $0$ if $\mathcal{X}$ and $\mathcal{Y}$ are linearly separable, and become larger the more "intertwined" they are. I do not have a precise definition of "intertwined" (if I did, the measure would follow easily!), but I would be happy with any reasonable one.
For bonus points, could the measure be extended to an arbitrary number of sets of points $k$, and/or to arbitrary dimension $n$?
Thanks in advance for any answers or references.
 A: Consider 
$$
\newcommand{\I}{\mathcal{I}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\CH}[1]{\mathrm{ConvexHull}\left(#1\right)}
\I(\X,\Y) = \frac{\Big(\mu\big(\CH{\X} \cap \CH{\X}\big)\Big)^2}{\mu\big(\CH{\X}\big) \cdot \mu\big(\CH{\Y}\big)}$$
where $\mu$ is the $n$-dimensional measure appropriate for space that contains $\X$ and $\Y$, and $\CH{A}$ is the convex hull of $A$, that is the smallest convex set that contains $A$ (i.e. the convex hull of three points is the whole triangle, not just the points).
This function $\I$ has maximum $1$ for $\CH{\X} = \CH{\Y}$ and minimum $0$ for sets such that the intersection of convex hulls has measure $0$. For example for $\X = [0,1]^2$ and $\Y = [-1,0]^2$ we have that $\X \cap \Y = \{(0,0)\}$ which has measure $0$, but $\X$ and $\Y$ are not linearly separable.
If you were to insist, this could be solved in two ways: 


*

*Instead of $\X$ work with $\{B(x,\varepsilon) \mid x \in \X\}$ with some small $\varepsilon$ of your choosing. This has the undesirable property of being positive for linearly separable sets with distance smaller than $\varepsilon$.

*Add some discontinuous component like 
$$f(\X,\Y) = 
\begin{cases}
0 &\text{ for } \CH{\X} \cap \CH{Y} = \varnothing \\
1 &\text{ for } \CH{\X} \cap \CH{Y} \neq \varnothing
\end{cases}$$

*Use multiple measures, that is, if $\mu_n$ is zero, maybe $\mu_{n-1}$ or $\ldots$ or $\mu_1$ or $\mu_0$ would be non-zero? You will need a few tweaks here (e.g. if one set is two-dimensional, the other is three-dimensional, and their intersection is one-dimensional), but it depends on what properties you would like to have.


I hope this helps $\ddot\smile$
