یک الگوریتم جدید برای نگهبانی سطوح نامنظم مثلث بندی شده
Publish place: 8th Annual Conference of Computer Society of Iran
Publish Year: 1381
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,593
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI08_047
تاریخ نمایه سازی: 18 بهمن 1386
Abstract:
در این مقاله یک الگوریتم جدید برای پوشش سطحی یک ناحیه ی مثلث بندی شده ارائه شده است که هنگام اجرای الگوریتم از دید سراسری رئوس استفاده می شود. در این الگوریتم ابتدا ناحیه ی مثلث بندی شده با حذف کردن تعدادی از رئوس آن به مجموعه ای از چند ضلعی های ساده تبدیل میشود وبه هر کدام از رئوس حذف شده یک نگهبان اختصاص می یابد. سپس مجموعه ی رئوس لازم برای نگهبانی مجموعه ی چند ضلعی های ساده که ناحیه ی بیرونی انها پیوسته است تعیین میشود. پس از ارائه ی الگوریتم و اثبات درستی آن، نشان می دهیم که این الگوریتم در زمان خطی نسبت به تعداد رئوس ناحیه ی مثلث بندی شده اجرا میشود و حد بالای تعداد نگهبان های انتخاب شده توسط آن [2n/3] می باشد. در عین حال اثبات شده است که با این الگوریتم حد بالای تعداد نگهبان ها در حالت متوسط [n/2] است.همچنین با توجه به ویژگی های الگوریتم، برای بهبودکارایی آن و استفاده از دید سراسری رئوس می توان با صرف هزینه ی زمانی بیشتری برای پیش پردازش تعداد نگهبان های انتخاب شده را کاهش داد.
Keywords:
Authors
علیرضا زارعی
دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف
محمد قدسی
دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :