Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions

Matching geometric objects with respect to their Hausdorff distance is a well investigated problem in Computational Geometry with various application areas. The variant investigated in this paper is motivated by the problem of determining a matching (in this context also called

registration

) for neurosurgical operations. The task is, given a sequence

$\mathcal{P}$

of weighted point sets (anatomic landmarks measured from a patient), a second sequence

$\mathcal{Q}$

of corresponding point sets (defined in a 3D model of the patient) and a transformation class

$\mathcal{T}$

, compute the transformations

$t\in\mathcal{T}$

that minimize the

weighted

directed Hausdorff distance of

$t(\mathcal{P})$

to

$\mathcal{Q}$

. The weighted Hausdorff distance, as introduced in this paper, takes the weights of the point sets into account. For this application, a weight reflects the precision with which a landmark can be measured.

We present an exact solution for translations in the plane, a simple 2-approximation as well as a FPTAS for translations in arbitrary dimension and a constant factor approximation for rigid motions in the plane or in ℝ

3

.