Skip to main content
1 of 4
gondolf
  • 1.5k
  • 9
  • 15

Clustering in Euclidean space

Suppose we are given points $P_1,\cdots,P_m$ in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1. An probability distribution $p_{i,j}$ is given for $1\leq i,j\leq m$.

For a given constant $\epsilon>0$, we have the following inequality holds $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Now the question is to ask whether it is always possible to clustering these points into groups such that

  1. Any two points in the same group has distance no more than $\epsilon'$, which only depends on $\epsilon$, not on $n,m$.

  2. The total joint probability between points of difference groups is less than $\delta$, which only depends on $\epsilon$, not on $n,m$.

gondolf
  • 1.5k
  • 9
  • 15