Computational Aspects of the Hausdorff Distance in Unbounded Dimension
König, Stefan
Original · EN
We study the computational complexity of determining the Hausdorff distance of two polytopes given in halfspace- or vertex-presentation in arbitrary dimension. Subsequently, a matching problem is investigated where a convex body is allowed to be homothetically 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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.