  We investigate the classes of functions whose minimization diagrams can be
approximated efficiently in \Re^d. We present a general framework and a
data-structure that can be used to approximate the minimization diagram of such
functions. The resulting data-structure has near linear size and can answer
queries in logarithmic time. Applications include approximating the Voronoi
diagram of (additively or multiplicatively) weighted points. Our technique also
works for more general distance functions, such as metrics induced by convex
bodies, and the nearest furthest-neighbor distance to a set of point sets.
Interestingly, our framework works also for distance functions that do not
comply with the triangle inequality. For many of these functions no near-linear
size approximation was known before.
