سال انتشار: ۱۳۸۳

محل انتشار: دهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۹

نویسنده(ها):

محمدرضا ضرابی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
محمد قدسی –

چکیده:

دراین مقاله الگوریتمی ارایه می کنیم که در زما و حافظه ی O(n کوتاهترین مسیر پیوندی بین دو نقطه ای دلخواه t,s در n ضلعی ساده p را با درنظر گرفتن شرط دیدن نقطه ی دلخواه q بدست آورد ب این شرط که حداقل یک نقطه روی مسیر جواب وجود داشته باشدکه از نقطه ی q قابل رویت باشد همچنین دراین مقاله این مساله را در حالت پرس و جو مورد بررسی قرار میدهیم به این صورت که پیش پردازش لازم بر روی p را طوری انجام دهیم که با دریافت هر سه نقطه ی t,s,q در زمان O(log n کوتاهترین مسیر پیوندی از s به t که q را ببیند بدست آورد.