The name coreset was suggested by Agarwal, Har-Peled, and Varadarajan in  as a small subset \(S\)  of points for a given input set \(P\) , such that any shape from a given family that covers \(S\)  will also cover \(P\) , after expanding the shape by a factor of \((1+\varepsilon )\) . In particular, the smallest shape that covers \(S\)  will be a good approximation for the smallest shape that covers \(P\) . For approximating different cost functions, e.g. the sum of distances to a given shape, we expect that the total weight of the sample will be similar to the number \(n\)  of input points. Hence, in their seminal work [1]}, Har-Peled and Mazumdar used multiplicative weights for each point in \(S\) , such that the weighted sum of distances from \(S\)  to a given shape from the family will approximate its sum of distances from the original data. In [1]} each shape in the family was actually a set of \(k\)  points, and the application was the classic \(k\) -means problem.
