본 논문에서는 두 개의 이차원 볼록 다각형간의 Hausdorff 거리를 계산하는 효율적인 알고리즘을 제안한다. 볼록 다각형을 k-DOP으로 바운딩하고, k-DOP의 방향성과 계층적인 특성에 따라 관심영역만을 추적하는 방법으로, 본 논문에서 제안하는 알고리즘은 평균적으로 O(logn)시간에 수행되며, 최악의 경우에도 O(n)의 수행성능을 보인다.
We present an efficient algorithm for computing the Hausdorff distance between two 2D convex polygons. Two convex polygons are bounded by k-DOPs and the regions of interest are traced using the orientational and hierarchical properties of k-DOP. The algorithm runs in a logarithmic time in the average case, and the worst case time complexity is linear.
