两张代数曲面之间Hausdorff距离的计算

：基于细分算法和区间算术，本文提出一种计算代数曲面间的Hausdorff 距离的新算法。该算法在计算出Hausdorff 距离近似值的同时能给出误差值。在理论上讲，只要设置的体素大小足够小，就可以使得计算出的Hausdorff 距离近似值与精确值之间的误差达到任意小。但具体计算的时候,如果精度要求较高则时间成本会变得很高。

Hausdorff 距离是两组点集之间相似程度的一种度量，它度量了两个点集间的最大不匹配程度。

Hausdorff 距离在计算机图形学、计算辅助几何设计、计算机视觉、图像处理等领域有十分重要的应用[1]。

已有的有关Hausdorff 距离的工作一般都是针对点集(图像)、多边形网格、或者参数曲线曲面提出来的。

早期Rucklidge[2]针对2 维图像提出了一种高效的Hausdorff 距离计算方法，但该方法很难推广到3 维。

Atallah[3]针对非相交平面凸多边形提出了一种计算时间为线性函数的Hausdorff 距离计算方法。

Barton 等[4]*项目基金：国家自然科学基金(No. 61272309, 61070135)。

407