Computational aspects of the Hausdorff distance in unbounded dimension

Stefan König


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.

Full Text:



ISSN: 1920-180X