# 两张代数曲面之间Hausdorff距离的计算Computing the Hausdorff Distance between Two Algebraic Surfaces

Abstract:
An algorithm for computing the approximate Hausdorff distance as well as its error value between two algebraic surfaces is proposed based on dividing and conquering subdivision technique and interval arithmetic. Theoretically, as long as the size of the voxels is small enough, the computed approximate Hausdorff distance can reach any precision, however, the CPU time used may be overwhelming.

[1] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2013) Efficient Hausdorff distance computation for freeform geometric models in close proximity. Computer Aided Design, 45, 270-276.

[2] Rucklidge, W. (1996) Efficient visual recognition using the Hausdorff distance. Lecture Notes in Computer Science, 1173, 1- 161.

[3] Atallah, M. (1983) A linear time algorithm for the Hausdorff distance between convex polygons. Information Processing Let- ters, 17, 207-209.

[4] Barton, M., Hanniel, I., Elber, G., et al. (2010) Precise Hausdorff distance computation between polygonal meshes. Computer Aided Geometric Design, 27, 580-591.

[5] Tang, M., Lee, M. and Kim, Y.-J. (2009) Interactive Hausdorff distance computation for general polygonal models. ACM Tran- sactions on Graphics, 28, 1-9.

[6] Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., et al. (2010) Precise Haus- dorff distance computation for planar freeform curves using biarcs and depth buffer. The Visual Computer, 26, 1007-1016.

[7] Bai, Y.-B., Yong, J.-H., Liu, C.-Y., et al. (2011) Polyline ap- proach for approximating the Hausdorff distance between two planar free-form curves. Computer Aided Design, 43, 687-698.

[8] Chen, X.-D., Ma, W., Xu, G., et al. (2010) Computing the Haus- dorff distance between two B-spline curves. Computer Aided Design, 42, 1197-1206.

[9] Hanniel, I., Krishnamurthy, A. and McMains, S. (2012) Com- puting the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU. Graphical Models, 74, 255-264.

[10] Jüttler, B. (2000) Bounding the Hausdorff distance of implicitly defined and/or parametric curves. Mathematical Methods in CAGD, 1-10.

[11] Li, Q.-D. and Tian, J. (2009) 2D piecewise algebraic splines for implicit modeling. ACM Transactions on Graphics, 28, 1-13.

[12] Shou, H.-H., Lin, H.-W., Ralph, M., et al. (2003) Modified af- fine arithmetic is more accurate than centered interval arithmetic or affine arithmetic. Lecture Notes in Computer Science, 2768, 355-365.

Top