Günter Rote:

Computing the minimum Hausdorff distance between two point sets on a line under translation

Information Processing Letters 38 (1991), 123–127, (Zbl 736.68078, MR #92d:68114). doi:10.1016/0020-0190(91)90233-8


Given two sets of points on a line, we want to translate one of them so that their Hausdorff distance is minimized. (The Hausdorff distance between two sets the maximum of the distances from a point in any of the two sets to the nearest point in the other set.) We present an optimal O(n log n) algorithm for this problem.
  PostScript file (gzipped)   pdf file   TeX .dvi file (gzipped)
other papers about this subject
Last update: August 16, 2004.