On the Budgeted Hausdorff Distance Problem

newcommandReℝ newcommandrealsℝ newcommandSetXmathsfX newcommandoptX[1]#1^star newcommandQoptMhoptXQ newcommandradr newcommandMh[1]#1 newcommandqueryq newcommandepsvarepsilon newcommandVorX[1]V pth#1 newcommandPolygonmathsfP newcommandIntRange[1][ #1 ] newcommandSpaceoverlinemathsfm newcommandpth[2][!]#1left(#2right) newcommandpolylogpolylog newcommandNmathbb N newcommandZmathbb Z newcommandptp newcommanddistY[2]left| #1 - #2 right| newcommandptqq newcommandRunningTimeObigl(n3/2 √k log3/2 n + kn log2 nbigr) newcommandptss Given a set P of n points in the plane, and a parameter k, we present an algorithm, whose running time is RunningTime, with high probability, that computes a subset Qopt subseteq P of k points, that minimizes the Hausdorff distance between the convex-hulls of Qopt and P. This is the first subquadratic algorithm for this problem if k is small.