Header menu link for other important links
A linear time deterministic algorithm to find a small subset that approximates the centroid
P. Worah,
Published in
Volume: 105
Issue: 1
Pages: 17 - 19
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.
About the journal
Published in
Open Access
Impact factor