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

چکیده انگلیسی
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
Journal: Journal of Complexity - Volume 29, Issues 3–4, June–August 2013, Pages 248–262
نویسندگان
Ker-I Ko,