A Minimax Model for Generalized Penetration Distance Between Convex Sets by Directed Hausdorff Distance

Abstract

The penetration distance, which characterizes the depth of intersection between two sets, is a fundamental computational geometry problem with a wide variety of applications in image processing, robotics, and circuit design. However, the penetration distance (even in Euclidean metric) is typically challenging to handle because it is essentially a nonconvex nonlinear optimization involving the projection onto the complement of a convex set. In this letter, we explore the penetration distance in non-Euclidean metrics (e.g., Manhattan, Chebyshev, and hexagon distances) by deploying the gauge function in convex analysis, and reformulate it as a nonlinear equation by virtue of the directed Hausdorff distance. More precisely, the generalized penetration distance amounts to seeking the largest zero point of a nondecreasing convex “black-box” function, whose function values can be obtained by the recent algorithmic advances in minimax optimization. We develop a solver for calculating generalized penetration distance between compact convex sets (possibly non-polyhedron) in arbitrary <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> dimension. Numerical experiments on variant types of compact convex sets demonstrate that the proposed solver is compelling to render solutions with high accuracy.