In the protein docking problem, pairs of molecules modeled as unions of balls are shape-matched by finding close but noncolliding positionings of the molecules. This provides one motivation for this work, which develops algorithms for four variations on finding the minimum Hausdorff distance under translation between two objects formed of unions of disks in ² or balls in ³.

The variation for which the authors obtain the most complete results uses a Hausdorff distance where the balls are treated as objects themselves with their own natural atom-to-atom distance function, rather than as sets of points.

Here, they obtain exact algorithms with complexity Õ(n³) in ² and Õ(n⁵) in ³ (where Õ ignores logarithmic factors) for n disks or balls. Their algorithms rely on combinatorial lemmas that support parametric search.

Treating the balls as sets of points leads to a rather different distance measure, for which they obtain the same complexity in ², but must resort to approximation in ³, because of the lack of understanding of the Voronoi diagram of balls. They also obtain approximation algorithms for distance-function variants that are not as sensitive to outliers.

The authors leave as the main open problem extending their work from translation only to all rigid motions.