Key points are not available for this paper at this time.
Given a set S of sources (points or segments), we consider the surface that is the graph of the functien d(z) = minPcS p(z, p), for some metric p. This surface is closely related to the Voronoi diagram, Vor(S), of S under the metric p. The upper envelope of a set of these Voronoi surfaces, each defined for a different set of sources, can be used to solve a number of problems, including finding the minimum Hausdorff distance between two sets of points or segments under translation, and determining the optimal placement of a site with respect to sets of utilities. ~7e derive bounds on the number of vertices on the upper envelope of m Voronoi surfaces, provide efficient algorithms to calculate these vertices, and discuss applications to the aforementioned problems.
Huttenlocher et al. (Tue,) studied this question.