Portal de Periódicos da CAPES

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

1991; Elsevier BV; Volume: 38; Issue: 3 Linguagem: Inglês

10.1016/0020-0190(91)90233-8

1872-6119

Günter Rote,

Digital Image Processing Techniques

Given two sets of points on a line, we want to translate one of them so that their Hausdorff distance (the maximum of the distances from a point in any of the sets to the nearest point in the other set) is as small as possible. We present an optimal O(n log n) algorithm for this problem.