k-Means: Random Sampling Procedure

• Optimal 1-Mean is

• Approximation of Centroid (Inaba et al)

• • S = random sample of size O(1/)
  • Centroid of S is a (1+)-approx centroid of P with constant probability