Computational aspects of the Hausdorff distance in unbounded dimension

Abstract

We study the computational complexity of determining the Hausdorff distance oftwo polytopes given in halfspace- or vertex-presentation in arbitrary dimension. Sub-sequently, a matching problem is investigated where a convex body is allowed to behomothetically transformed in order to minimize its Hausdorff distance to another one. For this problem, we characterize optimal solutions, deduce a Helly-type theorem and give polynomial time (approximation) algorithms for polytopes.