Take the 2-minute tour ×

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.

share|improve this question
Seems pretty straightforward. Are you looking for something other than the obvious order N^2 algorithm? –  Matthias Wandel Oct 31 '09 at 23:00
add comment

2 Answers

up vote 1 down vote accepted

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).

share|improve this answer
Yes exactly this was the idea came to my mind but didn't really grasp how to conditions in outer loop and inner, public double avgDistanceInCluster() { double avgDistance = 0.0; for (int i = 0; i < bigCluster.length; i++) { for (int j = i+1; j != bigCluster[i]; j++) { avgDistance = bigCluster[i] + bigCluster[j]/bigCluster.length; } } return avgDistance; } –  Null-Hypothesis Nov 1 '09 at 19:35
Sorry I added the four spaces for each line but formatting didn't work. –  Null-Hypothesis Nov 1 '09 at 19:35
add comment

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++) {
		for (int j = i+1; j < cluster.size(); j++) {
			avgDistance = (cluster.get(i) + cluster.get(j))/2; 
	Iterator<Double> iter = holder.iterator();
	double avgClusterDist = 0;
	while (iter.hasNext()) {
		avgClusterDist =+ holder.pop();
	return avgClusterDist/cluster.size();
share|improve this answer
bigCluster is an ArrayList, sorry forgot to define it, this is just a small part of a code that I am trying to build. –  Null-Hypothesis Nov 1 '09 at 21:55
My (edited version of your) example has different test in the first for loop, and calculates distances and averages differently. You want a distance between each pair of points, then add all the distances, and divide by the number of pairs of points. –  PanCrit Nov 2 '09 at 2:21
add comment

Your Answer


