Skip to main content
2 of 4
added 29 characters in body
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'$.

  2. The total joint probability between points of difference groups is less than $\delta$.

$\epsilon',\delta$ only depend on $\epsilon$, not on $n,m$. As long as $\epsilon$ goes to 0, $\epsilon',\delta$ go to 0.

gondolf
  • 1.5k
  • 9
  • 15