COMPUTING THE HAUSDORFF DISTANCE BETWEEN TWO SETS OF PARAMETRIC CURVES

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