International Conference on Science and Engineering in the Technology Era , 2017-03-11

عنوان : ( یافتن رئوس قابل دسترس از یک ربات محدود )

نویسندگان: محمد رضا رنجبر دیوکتی , مصطفی نوری بایگی ,
فایل: Full Text

استناددهی: BibTeX | EndNote

چکیده

مسئله قابل دید بودن رئوس موانع از یک نقطه یکی از مسائل معروف در حوزه هندسه محاسباتی است. در این مقاله ما تعریفی جدید از قابلیت دید بین دو نقطه ارائه می‌کنیم که در مسیریابی دسته‌ای خاص از ربات‌ها کاربرد دارد. در این تعریف دو نقطه نسبت به هم قابل دید هستند اگر زنجیره‌ای از پاره‌خط‌ها بین دو نقطه با حداکثر زاویه شکست محدود و رعایت حداقل فاصله بین دو شکست متوالی وجود داشته باشد که هیچ پاره‌خطی از این زنجیره با هیچ‌یک از یال‌های موانع برخورد نکند. سپس در ادامه الگوریتمی برای تعیین رئوس قابل دید از یک نقطه را بر اساس تعریف جدید ارائه می‌کنیم. نشان خواهیم داد با صرف زمان $O(n^\frac{4}{3} \log^c n)$ و حافظه $O(n^\frac{4}{3})$ می‌توان مسأله را حل کرد. در این رابطه‌ها $n$ تعداد رئوس مانع و $c$ یک عدد ثابت است. همچنین نشان می‌دهیم در صورتی که موانع از قبل مشخص باشند، می‌توان داده‌ساختاری را در مدت زمان $O(b \log^c)$ و با حافظه $O(b)$ تهیه کرد که با دریافت نقطه ناظر در زمان پرس‌وجو، رئوس قابل دید از نقطه را در زمان $O(n^2 \log^c n / \sqrt b)$ محاسبه کند. در این رابطه‌ها $b$ یک پارامتر دلخواه است که در شرط $n^\frac{4}{3} \le b \le n^2$ صدق می‌کند.

کلمات کلیدی

, طراحی مسیر, رباتیک, ربات
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1066313,
author = {رنجبر دیوکتی, محمد رضا and نوری بایگی, مصطفی},
title = {یافتن رئوس قابل دسترس از یک ربات محدود},
booktitle = {International Conference on Science and Engineering in the Technology Era},
year = {2017},
location = {اتريش},
keywords = {طراحی مسیر، رباتیک، ربات محدود},
}

[Download]

%0 Conference Proceedings
%T یافتن رئوس قابل دسترس از یک ربات محدود
%A رنجبر دیوکتی, محمد رضا
%A نوری بایگی, مصطفی
%J International Conference on Science and Engineering in the Technology Era
%D 2017

[Download]