Communications of the
Korean Mathematical Society CKMS

We present an algorithm for computing the Hausdorff distance between two parametric curves in $\R^n$, or more generally between two sets of parametric curves in $\R^n$. During repeated subdivision of the parameter space, we prune subintervals that cannot contain an optimal point. Typically, our algorithm costs $O(\log M)$ operations, compared with $O(M)$ operations for a direct, brute-force method, to achieve an accuracy of $O(M^{-1})$.

Keywords: Hausdorff distance, pruning technique