کوتاهترین مسیر پیوندی در یک چند ضلعی ساده با قید قابلیت دید

Publish Year: 1383
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 948

This Paper With 9 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

ACCSI10_209

تاریخ نمایه سازی: 25 آذر 1390

Abstract:

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

Authors

محمدرضا ضرابی

دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • _ R. Khosravi, M. Ghodsi. Shortest paths in sirple polygors ...
  • _ S. Suri. A linear _ algoritthm for ninimum link ...
  • S. Suri. On sorae link distance problem in i siple ...
  • _ _ Ekelsbrunner, L. Guibas, and J. Stolf, Optiral point ...
  • _ L.J. Guibas, J. Hershberger, D. Leven, _ Slarir, and ...
  • _ D.:T. Lee. Visibility of a sirple polygon. Comput. Vision ...
  • B. Chazelle, Triangulating a simple polygon in linear time, TDiscrete ...
  • _ L..J. uibas and J. Heshberger, Optimal shortest path queries ...
  • _ E.M. Arkin, J. S. B. Mitchell, S. Suri: Optimal ...
  • _ _ Elgirdy and D. Avis, A linear algorithm for ...
  • P. Bose, A. Lubiw, and J. I. Muunro. _ visibility ...
  • (1] J. S. B. Mitchell, G. Rote, and Woeginger, Mirinun-Link ...
  • نمایش کامل مراجع