# On the Budgeted Hausdorff Distance Problem

arXiv: https://arxiv.org/abs/2306.02151 · HTML: https://mlsanity.com/paper/2306.02151/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2023.

## Built on by (most cited first, 1 of 1)

- [ProHD: Projection-Based Hausdorff Distance Approximation](https://mlsanity.com/paper/2511.18207/) (2025)

## Abstract (arXiv)

 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.