Computational aspects of the Hausdorff distance in unbounded dimension

Stefan König

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v5i1a12

ISSN: 1920-180X