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

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

قابلیت دید، فاصله ی پیوندی، مسیر پیوندی