Unlike the notion of coresets in the next section, the idea of \(\varepsilon \) -approximations is known for decades [1]}, [2]}. In particular, unlike coresets, \(\varepsilon \) -approximations and \((\varepsilon ,\nu )\) -approximations in general, can be constructed using simple uniform random sampling of the points. The size of the sample depends linearly on the complexity of the queries in the sense soon to be defined in this section.
