Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a query point and receives a noisy version of its distance to the target. This problem arises naturally in various contexts ranging from localization in GPS and sensor networks to privacy-aware data access, and spans a wide variety of metric spaces. It is relevant from the perspective of both the reconstructor (seeking accurate recovery) and the responder (aiming to limit information disclosure, e.g., for privacy or security reasons). We study this reconstruction game through a learning-theoretic lens, focusing on the rate and limits of the best possible reconstruction error. Our first result provides a tight geometric characterization of the optimal error in terms of the Chebyshev radius, a classical concept from geometry. This characterization applies to all compact metric spaces (in fact, even to all totally bounded spaces) and yields explicit formulas for natural metric spaces. Our second result addresses the asymptotic behavior of reconstruction, distinguishing between pseudo-finite spaces -- where the optimal error is attained after finitely many queries -- and spaces where the approximation curve exhibits nontrivial decay. We characterize pseudo-finiteness for convex Euclidean spaces.

翻译：考虑利用近似距离查询定位未知目标点的任务：在每一轮中，重构器选择一个查询点，并接收其到目标点距离的含噪版本。该问题自然出现在从GPS与传感器网络定位到隐私感知数据访问等多种场景中，并涵盖广泛的度量空间。从重构器（追求精确恢复）和响应者（旨在限制信息泄露，例如出于隐私或安全原因）的视角来看，该问题均具有重要性。我们通过学习理论视角研究这一重构博弈，重点关注最佳可能重构误差的速率与极限。我们的首个结果利用切比雪夫半径（几何学中的经典概念）给出了最优误差的紧致几何刻画。该刻画适用于所有紧度量空间（实际上甚至适用于所有完全有界空间），并为自然度量空间提供了显式公式。我们的第二个结果探讨了重构的渐近行为，区分了伪有限空间（最优误差在有限次查询后达到）与近似曲线呈现非平凡衰减的空间。我们刻画了凸欧几里得空间的伪有限性。