There's an O(2^D * N) solution. Try thinking about the problem in 1d. the distance is |A[i].x - A[j].x|. If A[i].x >= A[j].x, then |A[i].x - A[j].x| = A[i].x - A[j].x . If A[j].x >= A[i].x, |A[i].x - A[j].x| = A[j].x - A[i].x. We can consider A[j].x < A[i].x and A[i].x >= A[j].x separately. Try increasing this to more dimensions.