We investigate the types of minimization diagrams(i.e., lower envelopes) that can be approximated efficiently in Rd(d is a constant). We present a new technique for computing approximate minimization diagrams, and we use it to build data-structures for generalized proximity search. The resulting data-structures have near linear size and can answer proximity queries in logarithmic time. For example, one can answer quickly proximity queries for multiplicative and additive weighted Voronoi diagrams, and Minkowski metrics for fat(convex) bodies. Our technique is more general, allowing more general distance functions.