Given a set of points S in any dimension, we describe a deterministic algorithm for finding a T ⊂ S, | T | = O (1 / ε) such that the centroid of T approximates the centroid of S within a factor 1 + ε for any fixed ε > 0. We achieve this in linear time by an efficient derandomization of the algorithm in [M. Inaba, N. Katoh, H. Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract), in: Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994, pp. 332-339]. © 2007 Elsevier B.V. All rights reserved.