how to find closely related values from a set?

Question

I have a set of values, for eg. {20, 1, 1, 21, 8, 22, 11, 40, 5, 21} and will need to find n closely related values. If n is 4 in the given example, the result should be {20, 21, 21, 22} because these are the closely related values (with least distance between them) in the given set.

It is possible to compare the number with each other and find the closely related ones. But this becomes cumbersome when the number of elements in set is large. Is there any optimal algorithm to do this?

Answer 1

Here is one way. For a multi-set of $n$ elements, selecting an $m$-subset:

1. Sort the multiset (this could be linear for integers or $n \log n$ for reals).
2. Take all differences of size $m$ in the sorted set (i.e. $e_{m}-e_1, e_{m+1} - e_2, \ldots$) and select the smallest one from these (a linear operation).

This last difference will represent $m$-subset of smallest radius.

Clearly, the answer need not be unique (e.g. a 2-subset from $\{1,2,2,1\}$ has 2 different answers of radius $0$). Total running time - $n \log n$.