Worah, Pratik ; Sen, Sandeep (2007) A linear time deterministic algorithm to find a small subset that approximates the centroid Information Processing Letters, 105 (1). pp. 17-19. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/j.ipl.2007.07.008
Abstract
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].
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Computational Geometry; Clustering; Derandomization |
| ID Code: | 53442 |
| Deposited On: | 08 Aug 2011 12:13 |
| Last Modified: | 08 Aug 2011 12:13 |
Repository Staff Only: item control page
