کوتاهترین مسیر پیوندی در یک چند ضلعی ساده با قید قابلیت دید
Publish place: 10th Annual Conference of Computer Society of Iran
Publish Year: 1383
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 948
This Paper With 9 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI10_209
تاریخ نمایه سازی: 25 آذر 1390
Abstract:
دراین مقاله الگوریتمی ارایه می کنیم که در زما و حافظه ی O(n کوتاهترین مسیر پیوندی بین دو نقطه ای دلخواه t,s در n ضلعی ساده p را با درنظر گرفتن شرط دیدن نقطه ی دلخواه q بدست آورد ب این شرط که حداقل یک نقطه روی مسیر جواب وجود داشته باشدکه از نقطه ی q قابل رویت باشد همچنین دراین مقاله این مساله را در حالت پرس و جو مورد بررسی قرار میدهیم به این صورت که پیش پردازش لازم بر روی p را طوری انجام دهیم که با دریافت هر سه نقطه ی t,s,q در زمان O(log n کوتاهترین مسیر پیوندی از s به t که q را ببیند بدست آورد.
Keywords:
Authors
محمدرضا ضرابی
دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :