We describe two data structures that preprocess a set S of n points in R(d) (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.

Additional Metadata
Keywords Clustering, Data structure, Facility location, Fermat-Weber center, Quadtree, Randomization, Range tree
Persistent URL dx.doi.org/10.1016/S0925-7721(02)00102-5
Journal Computational Geometry
Bose, P, Maheshwari, A, & Morin, P. (2003). Fast approximations for sums of distances, clustering and the Fermat-Weber problem. Computational Geometry, 24(3), 135–146. doi:10.1016/S0925-7721(02)00102-5