伪度量空间中点集直径近似的属性测试算法存在性问询

存在满足要求的属性测试算法，核心思路基于采样验证+伪度量的三角不等式性质设计，具体如下：

算法步骤 #

• 采样阶段：从点集P中独立随机采样$O(1/\varepsilon)$个点，记为样本集$S$。
• 验证阶段：
  1. 计算样本集$S$的直径（遍历$S$中所有点对，取最大伪度量距离）；
  2. 若$S$的直径$\leq D$，直接返回“yes”；
  3. 若$S$的直径$>2D$，统计P中与$S$内所有点的伪度量距离都$\leq2D$的点的数量；若该数量$\leq(1-\varepsilon)n$，返回“no”；
  4. 其余情况随机返回“yes”或“no”。

正确性验证 #

• 当P的直径$\leq D$时：样本集$S$的直径必然$\leq D$，算法一定会返回“yes”，满足至少2/3概率的要求。
• 当P的直径$>2D$且无法通过移除$\varepsilon n$个点使直径$\leq2D$时：此时不存在大小为$(1-\varepsilon)n$的子集其直径$\leq2D$。样本集$S$中必然存在至少一对点的距离$>2D$（否则$S$的直径$\leq2D$，对应的包含$S$的最大子集若直径$\leq2D$，大小会超过$(1-\varepsilon)n$，与前提矛盾）。进一步，当$S$中存在距离$>2D$的点对时，P中能同时与这两个点距离$\leq2D$的点数量必然不足$(1-\varepsilon)n$，因此算法返回“no”的概率$\geq2/3$。
• 其他情况：按规则随机返回，符合题目对结果无要求的设定。

时间复杂度 #

采样阶段仅需$O(1/\varepsilon)$次随机选取；验证阶段中，样本集大小为$O(1/\varepsilon)$，点对遍历是$O((1/\varepsilon)^2)$，统计符合条件的点是$O(n/\varepsilon)$，整体时间复杂度为$O(n/\varepsilon)$，远优于经典的$O(nd)$算法，符合属性测试的高效性要求。

注：伪度量的三角不等式性质是验证阶段距离关系推导的核心依据，确保了统计逻辑的合理性。

内容的提问来源于stack exchange，提问作者usul