As the image presented below, the reddish point set is totally separated from the blueish one and the greenish one, while the blueish point set is quite mixed with the greenish one.

A number of point sets on the plane. Each point set takes up a simply connected domain concave or convex. The points' coordinates is known and the points are not necessarily on the grid which might be implied by the image. The separation or mixture degree of two sets is all that matters.

How to value the extent of separation or mixing of point sets? Any suggestion or reference will be greatly appreciated. Statistical method would be preferred if optional.

enter image description here


One can define the degree of separation between the classes of points based on the power means \begin{equation} M_p(X):=\Big(\frac1N\,\sum_1^N x_i^p\Big)^{1/p}, \end{equation} where $X=(x_i)_1^N$ is a finite family of nonnegative real numbers and $p$ is a real number. As $p$ increases from $-\infty$ to $0$ to $\infty$, $M_p(X)$ increases from $M_{-\infty}(X):=\min_1^N x_i$ to $M_0(X):=(\prod_1^N x_i)^{1/N}$ to $M_\infty(X):=\max_1^N x_i$.

For sets $A$ and $B$ of points on the plane, a "distance" function $d$, and parameters $p,q,r,t,u,v$ in $[-\infty,\infty]$, define the $p$-size
\begin{equation} s_p(A):=M_p((d(a,b)\colon a\in A,b\in A)) \end{equation} of $A$ (one may take $p=0.5$ or even $p=0.1$ to decrease the influence of outliers); the $q$-distance \begin{equation} d_q(a,B):=M_q((d(a,b)\colon b\in B)) \end{equation} from a point $a$ to the set $B$ (one may take e.g. $q=-1$, to imitate the minimum, in a softer fashion); the $(q,r)$-distance \begin{equation} h_{q,r}(A,B):=M_r((d_q(a,B)\colon a\in A)) \end{equation} from the set $A$ to the set $B$ (one may take $r=0.5$); the $t$-symmetrization \begin{equation} H_{q,r,t}(A,B):=M_t((h_{q,r}(A,B),h_{q,r}(B,A))) \end{equation} of $h_{q,r}(A,B)$ (a $(q,r,t)$-generalization of the Hausdorff distance; one may take $t=1$); and the $(p,q,r,t,u)$-separation \begin{equation} S_{p,q,r,t,u}(A,B):=\frac{H_{q,r,t}(A,B)}{M_u((s_p(A),s_p(B)))} \end{equation} between the sets $A$ and $B$ (one may take $u=1$). Finally, for classes $C_1,\dots,C_k$ of points, define the overall $(p,q,r,t,u,v)$-degree of separation \begin{equation} S_{p,q,r,t,u,v}(C_1,\dots,C_k):=M_v((S_{p,q,r,t,u}(C_i,C_j)\colon1\le i<j\le k)) \end{equation} (one may take $v=-1$).

(For even more flexibility, one may use "distance" functions other than the Euclidean one. One can also use, instead of or in addition to the power means, the median and its various generalizations, as well as various trimmed and Winzorized means.)

As an example, for the four classes of points in each of the two pictures here, we have the values of the degree $S_{p,q,r,t,u,v}(C_1,\dots,C_4)$ of separation equal about $3.326$ and $1.872$, respectively, with $(p,q,r,t,u,v)=(0.5, -1, 0.5, 1, 1, -1)$ and the Euclidean distance for $d$. The second picture is obtained from the first (left) one by moving the blue set to the left and the yellow set down, both then closer to the green set; that decreases the overall degree of separation from $3.326$ to $1.872$.

enter image description here

  • $\begingroup$ Thanks for your great answer! The clustering algorithms might not be helpful because the point sets are not expected to break up and regroup. The formula given is not robust when some noisy point is far away from its set's main body, The separation degree is an average distance and not dimensionless. For example, When the reddish point set in the image grows to the north or shrink, the separation degree to the blueish one would change larger and smaller but in fact they keep total disjoint. And the value could smaller than the value of some totally mixed but large sets. $\endgroup$ – rube wang Aug 20 '18 at 22:07
  • 1
    $\begingroup$ I have given a version of the measure of separation that is flexible, dimensionless, and can be made as robust as one wants. $\endgroup$ – Iosif Pinelis Aug 21 '18 at 14:08
  • $\begingroup$ I think that is exactly what I want. Thank you! $\endgroup$ – rube wang Aug 22 '18 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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