Geometry is everywhere, part XLVII
Kenneth L. Clarkson · 2008
The idea of a metric space is among the most basic of geometric concepts, and so appears in a great variety of applications and algorithms, sometimes in disguise. For a given metric, the idea of a net, in the general sense of a "collection of nicely distributed points," appears naturally, but there are many conceptions of what it means to be nicely distributed; often this is a function of a parameter ε > 0, which might be for example the minimum distance between pairs of points in the net. For a given version of nets, the idea of dimension appears naturally, as the exponent in the growth rate of nets as a function of ε, while measures on metric spaces give the constant factor in that growth rate. As the parameter ε is varied, the scale of relevant "features" of the metric space changes; that is, variation in ε is a simple form of "multi-resolution analysis." I will survey a little bit of the wealth of variations and implications of these beautiful ideas, both those familiar to the SOCG community and those a little more obscure, with such topics as: the greedy algorithm and other algorithms for building nets; curvature-based metrics; the energy dimension and its relation to random projection; the interplay between continuous concepts and discrete applications; and different versions of multi-resolution.