«مسیریابی» همواره به عنوان یکی از مسائل اساسی و مهم در علوم کامپیوتری به شمار می‌رود و در بسیاری از زمینه‌ها از جمله رباتیک و شبکه‌های بی‌سیم کاربرد دارد. این مسئله اغلب در یک فضای هندسی که توسط یک «گراف هندسی» قابل مدل‌سازی است مطرح می‌شود، یکی از مفیدترین انواع گراف‌های هندسی که ویژگی‌های مفیدی جهت سهولت مسیریابی در بر دارد «مثلث‌بندی دلانی» است. هنگامی که اطلاعات کاملی از گراف مورد نظر در دسترس باشد با استفاده از الگوریتم‌های پیدا کردن مسیر بهینه در گراف‌های جهت‌دار از جمله Dijkstra می‌توان به مسیر بهینه رسید، اما در حالت «برخط» که اطلاعات موجود محدود هستند و در هر مرحله انتخاب بسته/ربات مورد نظر باید فقط بر اساس اطلاعات محلی صورت بگیرد، مسئله‌ با چالش‌های بیشتری روبرو می‌گردد. در این مقاله، ما چهار الگوریتم برخط با پیچیدگی حافظه O(1) برای مثلث‌بندی‌های دلانی را ارائه نموده و با مقایسه‌ی عملکرد آن‌ها با الگوریتم‌های مشابه روی نمونه‌های شبیه‌سازی‌شده، آن‌ها را ارزیابی می‌نماییم. نتایج به دست آمده در آزمایشات ما نشان می‌دهند که الگوریتم‌های جدید در عین حفظ سادگی و آسان بودن پیاده‌سازی، عملکرد بیشتر الگوریتم‌های مشابه موجود را بهبود می‌دهند.

کلمات کلیدی