# Nearest/farthest neighbour between-group distance: an efficient way to find it

This question might be better suited for StackOverflow as it is programming (so you are free to suggest to move it), but it is about a data analysis programming task.

The Q: do you know any "elegant" (e.g. either fast or syntactically parsimonious) way to know the minimal (nearest neighbour) distance between groups/classes without explicit taking pairs of groups via loop? And likewise the same Q about maximal (farthest neighbour) distance.

Let $\bf D$ be the square symmetric matrix of distances (any kind of dissimilarities) between points. $\bf g$ be the grouping variable with $k$ labels; each point belongs to one group. Of course, the design matrix (dummy variables) $\bf G$ can be created from $\bf g$ if needed. Example of data:

    D                                 g      G
1   2   3   4   5   6   7   8          a b c
(a) (a) (b) (a) (c) (b) (b) (c)
1   0   9   29  45  30  77  75  52    a    1 0 0
2   9   0   40  54  9   68  56  41    a    1 0 0
3   29  40  0   14  49  44  32  21    b    0 1 0
4   45  54  14  0   75  98  38  41    a    1 0 0
5   30  9   49  75  0   41  43  26    c    0 0 1
6   77  68  44  98  41  0   44  20    b    0 1 0
7   75  56  32  38  43  44  0   5     b    0 1 0
8   52  41  21  41  26  20  5   0     c    0 0 1


The minimal distance between groups a and b is 14, between groups a and c is 9, and between b and c is 5. It is quite straightforward to establish it by considering the groups pair by pair. Upon taking a pair, one can cut out the submatrix of distances corresponding to the between-group distances of the two groups and call the matrix min function; or can zero-off or replace all the distances in the matrix except those between-group ones and call the matrix min function. (Zeros on the diagonal could be replaced too, not to interfere.)

Maybe for some reason I don't want to undertake the looping through the $k(k-1)/2$ pairs of groups. Could there be an alternative way? Do you have ideas?

And in general: what would be your fastest way to solve the task? $\bf D$ could be say up to 10000 size and $k$ up to 100 or so.

[My Q was motivated by the fact that in case we want sum (or average) distance between groups the problem is solved syntactically in just one line as $\bf G'DG$. With minimal (or maximal) distance the problem is open to me; I want to consider among approaches to choose the fastest or the parsimoniest. Note: I won't be programming on a "low-level" language such as Fortran or C, rather, language such as Matlab, R, or SPSS syntax will be used. Basic Matrix/linear algebra functions are available.]

• There are many efficient algorithms that exploit special properties of the distance. It also matters whether you need to perform your nearest-group calculation once or repeatedly. For repeated calculations, it can pay to perform expensive precomputations. For instance, if it's known these are Euclidean distances, then a perfect MDS solution for the points will exist. Construct the nearest-neighbor and farthest-neighbor Voronoi diagrams for one such a solution: they can be exploited to achieve $O(k\log(k))$ performance instead of $O(k^2)$. – whuber Aug 29 '16 at 14:23
• @whuber, thank much you for the comment. Answering: Distances can be any dissimilarities, not just euclidean (so MDS probably won't help). The task is one-occasion: construct the k x k matrix of between-group minimal distances; end of task. A solution via Voronoi has not been considered by me, an answer on such an option is welcome. – ttnphns Aug 29 '16 at 15:00