Ik-Sung Kim and William McLean Korea Maritime University, The University of New South Wales
Abstract : 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})$.