## 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.