This paper presents efficient algorithms for computing new types of distance measures. One of the measures denoted by drho+(A,B) characterizes proximity of non-intersecting objects A and B taking into account their shapes. The second measure denoted by δ(σ;A,B) characterizes the penetration between two intersecting objects. The main contributions include (a) O(m log n+n log m) algorithms to compute drho+(A,B) and δ(σ;A,B) between convex polyhedra in R3 having m and n vertices respectively (b) an efficient procedure to compute δ(σ;A,B) between non-polygonal objects described algebraically. We point out the utility of the measures for collision detection between a pair of objects.