Computational Aspects of the Hausdorff Distance in Unbounded Dimension

Abstract

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.

Cited by in corpus (2)

• Breaking the Curse of Dimensionality with Convex Neural Networks
• Convex Hull Approximation of Nearly Optimal Lasso Solutions