Given a set S of sources (points or segments) in R(d), we consider the
surface in R(d+1) that is the graph of the function d(x) = min(p is-a
n-element-of s) rho(x, p) for some metric rho. This surface is closely
related to the Voronoi diagram, Vor(S), of S under the metric rho. Th
e upper envelope of a set of these Voronoi surfaces, each defined for
a different set of sources, can be used to solve the problem of findin
g the minimum Hausdorff distance between two sets of points or line se
gments under translation. We derive bounds on the number of vertices o
n the upper envelope of a collection of Voronoi surfaces, and provide
efficient algorithms to calculate these vertices. We then discuss appl
ications of the methods to the problems of finding the minimum Hausdor
ff distance under translation, between sets of points and segments.