Computation of the Hausdorff Distance between Two Compact Convex Sets

Area of Science:

• Computational Geometry
• Optimization Algorithms
• Convex Analysis

Background:

• The Hausdorff distance is crucial in theory and practice, but generic algorithms are lacking for infinite sets.
• Infinite sets defined by algebraic equations and inequalities present a significant computational challenge.

Purpose of the Study:

• To develop novel algorithms for computing the Hausdorff distance between compact convex sets.
• To address the limitations of existing methods, particularly for infinite sets.

Main Methods:

• Construction of Frank-Wolfe and projected gradient ascent algorithms.
• Investigation of a homotopy method to overcome local maxima issues.
• Testing algorithms on specific pairs of compact convex sets, including a box and a non-negative orthant intersection, and a probability simplex and a translated ball.

Main Results:

• Projected gradient ascent proved more reliable than Frank-Wolfe, finding the exact Hausdorff distance for one problem analytically.
• The homotopy method improved algorithm performance, especially when exact solutions were difficult to attain.
• Demonstrated the effectiveness of the proposed methods on challenging geometric shapes.

Conclusions:

• The developed Frank-Wolfe and projected gradient ascent algorithms, enhanced by a homotopy method, provide a viable approach for computing Hausdorff distance between compact convex sets.
• These methods fill a critical gap in computational geometry for handling infinite sets.
• Projected gradient ascent shows superior reliability for certain problems.