کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4608739 1631471 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of computing the Hausdorff distance
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 29, Issues 3–4, June–August 2013, Pages 248–262
نویسندگان
,