豪斯多夫距离

豪斯多夫距离（Hausdorff distance）衡量两个集合在同一度量空间中相互接近的程度。先从第一个集合的每一点寻找第二个集合中的最近距离，再取其中的最大偏差；反方向重复一次，最后取两者较大值。它比较的是集合的位置与覆盖程度，不要求预先指定一一对应的点。

例如在欧氏平面中取 $A=\{(0,0),(2,0),(0,2)\}$、$B=\{(0,0),(2,1)\}$。从 $A$ 看向 $B$，最远的遗漏来自 $(0,2)$，最近距离为二；从 $B$ 看向 $A$，最大最近距离却只有一。两个方向回答不同的问题。

从点到集合，再比较两个方向

设 $(X,d)$ 是度量空间，$A,B\subset X$ 非空。点到集合的距离定义为 $$d(x,B)=\underset{b\in B}{inf}d(x,b).$$ 下确界先找最靠近 $x$ 的位置。随后定义有向偏差与对称距离 $$h(A,B)=\underset{a\in A}{sup}d(a,B),d_H(A,B)=max\{h(A,B),h(B,A)\}.$$ 当两集合都有界时，这些量有限；不加有界限制时允许取无穷，例如 $d_H(ℝ,\{0\})=\mathrm{\infty }$。有向量 $h$ 一般不对称，所以单独一项不能当作集合上的度量。

对有限集合，内层下确界和外层上确界都能直接改成最小值、最大值。主例的全部点对平方距离如下：

$d(a,b{)}^2$	$b_0=(0,0)$	$b_1=(2,1)$	行最小值
$a_0=(0,0)$	0	5	0
$a_1=(2,0)$	4	1	1
$a_2=(0,2)$	4	5	4
列最小值	0	1

先取每行最小值，再取最大值得四，开平方后 $h(A,B)=2$。每列最小值的最大值为一，所以 $h(B,A)=1$，最终 $d_H(A,B)=2$。平方与开平方都在非负数上保持大小顺序，因而可以先用平方距离准确比较。

实线箭头展示A到B的最近距离，虚线反向箭头展示B到A。相同的最近邻点可以被重复使用，这不是一一匹配。

距离也可解释为双向覆盖。对 $r\ge 0$，定义闭距离邻域 $B^{[r]}=\{x\in X:d(x,B)\le r\}$，则 $$d_H(A,B)\le r⟺A\subseteq B^{[r]}\text{且}B\subseteq A^{[r]}.$$ 在紧集或有限点集的情形，最近点存在，这还等价于每一点都能在另一集合找到一个距离不超过 $r$ 的点。研究点集图像比较的 Cornell 页面以最近邻和双向邻域解释这一含义。

闭包、紧性与度量性质

点到集合的距离只看得到闭包。事实上，对任意 $x,y\in X$，三角不等式取下确界后给出 $$d(x,B)\le d(x,y)+d(y,B),|d(x,B)-d(y,B)|\le d(x,y).$$ 所以距离函数连续。将 $B$ 换成闭包不改变下确界，再由连续性把外层上确界的集合 $A$ 换成闭包，得到 $$d_H(A,B)=d_H(\bar{A},\bar{B}).$$ 因此，对任意非空有界集合，$d_H(A,B)=0$ 恰好表示两者闭包相等，并不必然表示集合本身相等。例如 $(0,1)$ 与 $[0,1]$ 的距离为零。

限制到非空闭有界子集后，零距离才强迫集合相等。非负性和对称性已包含在定义中，三角不等式还需验证。取第三个非空有界集合 $C$，固定 $a\in A$ 和 $\eta >0$，按下确界定义选择 $b\in B$，使 $d(a,b)<d(a,B)+\eta$。于是 $$d(a,C)\le d(a,b)+d(b,C)\le d(a,B)+\eta +h(B,C).$$ 先令 $\eta \downarrow 0$，再对 $a\in A$ 取上确界，得到 $h(A,C)\le h(A,B)+h(B,C)$。反向同理，因而 $$d_H(A,C)\le d_H(A,B)+d_H(B,C).$$ 这证明了闭有界子集上的度量性质；用任意小的 $\eta$，也避免了擅自假定最近点一定存在。

紧性与闭有界性作用不同。 紧集自动闭且有界；对两个非空紧集，连续距离函数在紧集上达到最小值与最大值，所以定义中的最近点和最坏点都存在。在欧氏有限维空间中，闭有界集就是紧集；一般度量空间没有这个等价关系。本篇的度量证明只需闭有界，而将下确界、上确界写成实际达到的最小值、最大值时使用了紧性。

空集不属于上述度量空间。若另作扩展，可约定 $d_H(\varnothing ,\varnothing )=0$，空集与非空集的距离为无穷；下面的有限点集程序直接拒绝空输入。

测量误差怎样传到集合距离

设 $A,B,A^{\prime },B^{\prime }$ 都是非空紧集，分别有已知误差界 $d_H(A,A^{\prime })\le \alpha$、$d_H(B,B^{\prime })\le \beta$。两次三角不等式给出 $$d_H(A,B)\le \alpha +d_H(A^{\prime },B^{\prime })+\beta .$$ 交换原集合和近似集合再用一次，就得到稳定性估计 $$|d_H(A,B)-d_H(A^{\prime },B^{\prime })|\le \alpha +\beta .$$ 如果有限点集的每个点都有对应的测量点，且逐点偏移不超过 $\alpha$，则这个对应关系给出两个方向的覆盖，从而确有 $d_H(A,A^{\prime })\le \alpha$；对应点不必仍是新的最近邻。

在主例中，把 $a_2$ 改为 $a{\text{'}}_2=(0,9/4)$，把 $b_1$ 改为 $b{\text{'}}_1=(2,11/10)$，其他点不动。逐点偏移给 $\alpha =1/4,\beta =1/10$，所以距离变化至多 $7/20$。直接重算可得 $h(A^{\prime },B^{\prime })=9/4$、$h(B^{\prime },A^{\prime })=11/10$，故新距离为 $9/4$，实际改变量 $1/4$ 落在所证界内。

两侧集合的误差相加，给出距离估计的误差带。这里的横轴是集合距离，不是原点集的空间坐标。

有解变式。 保持原来的 $A$，将 $B$ 加入离群点 $(10,0)$。原来各点到 $B$ 的最近距离不会增加，最大值仍为二；新点到 $A$ 的最近点是 $(2,0)$，距离八。因此新 Hausdorff 距离为八。最大偏差对单个离群点敏感，正是该定义的性质。用分位数或平均值替换最大值，会改变所回答的问题，通常也不再保留这里的全部度量性质。

有限样本与连续实体

两个样本集合很近，并不单独保证它们代表的实体很近。令 $S$ 为从 $(0,0)$ 到 $(2,0)$ 的线段，$T$ 为从 $(0,0)$ 经 $(1,1)$ 到 $(2,0)$ 的两段折线。若只采两端点，两者的样本集合完全相同，样本距离为零。

但 $T$ 的顶点到 $S$ 距离为一，且其余折线点到 $S$ 的距离不超过一，所以 $h(T,S)=1$。对 $(x,0)\in S$，到两条斜线段的较小距离是 $min\{x,2-x\}/\sqrt{2}$，最大值在中点达到 $1/\sqrt{2}$。因此 $d_H(S,T)=1$。

只比较两端点会得到零，比较完整线段和折线得到一。连接样本的方式已经改变了被比较的集合。

若有限样本 $P\subset S,Q\subset T$ 另外具有覆盖证书：每个实体点到本侧样本的距离分别不超过 ${\eta }_P,{\eta }_Q$，那么 $d_H(S,P)\le {\eta }_P$、$d_H(T,Q)\le {\eta }_Q$。上一节的稳定性才给出 $$|d_H(S,T)-d_H(P,Q)|\le {\eta }_P+{\eta }_Q.$$ 这项覆盖要求包括实体未被采到的部分。仅有点云的外观、点数或两侧都采样的事实，还没有给出这两个误差常数。

精确有限点集计算

下面计算有限有理坐标点集的欧氏平方距离。输入必须非空，各点维数相同且为正；坐标接受整数、有理数字符串或 Fraction，拒绝普通浮点数、NaN、无穷和布尔值。返回两个有向平方偏差、对称平方距离和实现最大值的一对点索引；索引对应输入顺序。重复点不影响距离，多个最近点并列时取先出现者。程序不改写输入。

Python 3

from fractions import Fraction

def exact_coordinate(value):
    if isinstance(value, bool) or not isinstance(value, (int, str, Fraction)):
        raise TypeError("use integer, rational string or Fraction coordinates")
    try:
        return Fraction(value)
    except (ValueError, ZeroDivisionError) as error:
        raise ValueError("finite rational coordinate required") from error

def hausdorff_squared(A, B):
    P = tuple(tuple(exact_coordinate(v) for v in point) for point in A)
    Q = tuple(tuple(exact_coordinate(v) for v in point) for point in B)
    if not P or not Q:
        raise ValueError("nonempty finite point sets required")
    dimension = len(P[0])
    if dimension == 0 or any(len(p) != dimension for p in P+Q):
        raise ValueError("common positive coordinate dimension required")
    column_min = [None]*len(Q)
    column_match = [None]*len(Q)
    row_min, row_match = [], []
    for i, p in enumerate(P):
        best, match = None, None
        for j, q in enumerate(Q):
            squared = sum((u-v)**2 for u, v in zip(p, q))
            if best is None or squared < best:
                best, match = squared, j
            if column_min[j] is None or squared < column_min[j]:
                column_min[j], column_match[j] = squared, i
        row_min.append(best)
        row_match.append(match)
    i = max(range(len(P)), key=row_min.__getitem__)
    j = max(range(len(Q)), key=column_min.__getitem__)
    return {"h_ab_squared": row_min[i],
            "h_ba_squared": column_min[j],
            "hausdorff_squared": max(row_min[i], column_min[j]),
            "witness_ab": (i, row_match[i]),
            "witness_ba": (column_match[j], j)}

A = [(0, 0), (2, 0), (0, 2)]
B = [(0, 0), (2, 1)]
result = hausdorff_squared(A, B)
assert (result["h_ab_squared"], result["h_ba_squared"],
        result["hausdorff_squared"]) == (4, 1, 4)
assert result["witness_ab"] == (2, 0)
assert hausdorff_squared([(0, 0)], [(0, 0), (3, 4)])["hausdorff_squared"] == 25
assert hausdorff_squared([(1,), (1,)], [(1,)])["hausdorff_squared"] == 0
print(result)

正确性来自两层最小值的不变量：扫描一行时，best 是该行已经检查过的点对平方距离的最小值；扫描到第 $i$ 行后，column_min[j] 是前面各行到 $q_j$ 的最小值。全部扫描完毕，两个数组分别就是行最小值和列最小值。最后取最大值，正好对应定义中的两次有向偏差。返回的平方值本身一般不满足三角不等式，例如单点集零、一、二之间会有 $4>1+1$。取平方根后才得到 $d_H$；若平方根无理，普通浮点开方只是数值近似。

设两侧有 $m,n$ 个点，每点 $k$ 个坐标。程序进行 $mn$ 次点对比较，每次用 $O(k)$ 次有理数运算，总计 $O(mnk)$ 次运算；不存整张距离表，复制坐标与保存行列状态共需 $O(k(m+n))$ 个数和索引。有理数位长增长仍影响实际运算成本。计算对象是所给有限点集；折线、曲面或配准后的最小距离属于另外的几何计算问题。