  We present a new algorithm, trimed, for obtaining the medoid of a set, that
is the element of the set which minimises the mean distance to all other
elements. The algorithm is shown to have, under certain assumptions, expected
run time O(N^(3/2)) in R^d where N is the set size, making it the first
sub-quadratic exact medoid algorithm for d>1. Experiments show that it performs
very well on spatial network data, frequently requiring two orders of magnitude
fewer distance calculations than state-of-the-art approximate algorithms. As an
application, we show how trimed can be used as a component in an accelerated
K-medoids algorithm, and then how it can be relaxed to obtain further
computational gains with only a minor loss in cluster quality.
