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
Abstract
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.
Last update: August 16, 2004.