On the complexity of computing the Hausdorff distance

We study the computational complexity of the Hausdorff distance of two curves on the two-dimensional plane, in the context of the Turing machine-based complexity theory of real functions. It is proved that the Hausdorff distance of any two polynomial-time computable curves is a left-Σ2P real number. Conversely, for any tally set AA in Σ2P, there exist two polynomial-time computable curves such that set AA is computable in polynomial time relative to the Hausdorff distance of these two curves. More generally, we show that, for any set AA in Σ2P, there exist two polynomial-time computable curves such that set AA is computable in polynomial time relative to the Hausdorff distances of subcurves of these two curves.