Avg distance between points in a cluster

Question

Sounds like I got the concept but cant seems to get the implementation correct. eI have a cluster (an ArrayList) with multiple points, and I want to calculate avg distance. Ex: Points in cluster (A, B, C, D, E, F, ... , n), Distance A-B, Distance A-C, Distance A-D, ... Distance A,N, Distance (B,C) Distance (B,D)... Distance (B,N)...

Thanks in advance.

Answer 1

You don't want to double count any segment, so your algorithm should be a double for loop. The outer loop goes from A to M (you don't need to check N, because there'll be nothing left for it to connect to), each time looping from curPoint to N, calculating each distance. You add all the distances, and divide by the number of points (n-1)^2/2. Should be pretty simple.

There aren't any standard algorithms for improving on this that I'm aware of, and this isn't a widely studied problem. I'd guess that you could get a pretty reasonable estimate (if an estimate is useful) by sampling distances from each point to a handful of others. But that's a guess.

(After seeing your code example) Here's another try:

public double avgDistanceInCluster() { 
    double totDistance = 0.0; 
    for (int i = 0; i < bigCluster.length - 1; i++) { 
        for (int j = i+1; j < bigCluster.length; j++) { 
            totDistance += distance(bigCluster[i], bigCluster[j]);
        }
    }
    return totDistance / (bigCluster.length * (bigCluster.length - 1)) / 2; 
}

Notice that the limit for the first loop is different. Distance between two points is probably sqrt((x1 - x2)^2 + (y1 -y2)^2).

Answer 2

THanks for all the help, Sometimes after explaining the question on forum answer just popup to your mind. This is what I end up doing.

I have a cluster of point, and I need to calculate the avg distance of points (pairs) in the cluster. So, this is what I did. I am sure someone will come with a better answer if so please drop a note. Thanks in advance.

/**
 * Calculate avg distance between points in cluster
 * @return
 */
public double avgDistanceInCluster() {
 double avgDistance = 0.0;
 Stack<Double> holder = new Stack<Double>();
 for (int i = 0; i < cluster.size(); i++) {
  System.out.println(cluster.get(i));
  for (int j = i+1; j < cluster.size(); j++) {
   avgDistance = (cluster.get(i) + cluster.get(j))/2; 
   holder.push(avgDistance);
  }
 }
 Iterator<Double> iter = holder.iterator();
 double avgClusterDist = 0;
 while (iter.hasNext()) {
  avgClusterDist =+ holder.pop();
  System.out.println(avgClusterDist);
 }
 return avgClusterDist/cluster.size();
}