On the Budgeted Hausdorff Distance Problem

2025/05/11 by Har-Peled, Sariel, Raichel, Benjamin

paper · doi:10.57717/cgt.v4i2.57

Abstract

Given a set P of n points in the plane, and a parameter k, we present an algorithm, whose running time is O(n3/2 √k log3/2n + kn log2n), with high probability, that computes a subset Q* of P of k points, that minimizes the Hausdorff distance between the convex-hulls of Q* and P . This is the first subquadratic algorithm for this problem if k is small.

Related

• On the Budgeted Hausdorff Distance Problem
• Fast and Exact Convex Hull Simplification
• A sharp p-subadditive bound for the l_p Hausdorff distance from convex hull
• Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem
• Approximating the Directed Hausdorff Distance