Fast approximations for sums of distances, clustering and the Fermat–Weber problem

We describe two data structures that preprocess a set S of n points in (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of . This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(nlogn) time deterministic and O(n) time randomized -approximation algorithm for the so called Fermat–Weber problem in any fixed dimension.