کوتاهترین مسیر برفراز یک زمین چند وجهی

دراین مقاله مساله ی یافتن کوتاهترین مسیر برفراز یک زمین چند وجهی مورد مطالعه قرار گرفته و دو الگوریتم تقریبی جدید برای مساله ارائه شده است الگوریتم اول در زمان (فرمول در متن مقاله ) یک مسیر تقریبی را که طول آن حداکثر 1+e برابر طول کوتاه ترین مسیر L1 برفراز یک زمین چند وجهی است به دست می آورد n تعداد راسهای زمین و N حداکثر تعداد بیتهای مورد نیاز برای نمایش مختصات راس هاست الگوریتم دوم بر پایه ی الگوریتم قبل یک مسیر تقریبی را که طول آن حداکثر (فرمول در متن مقاله ) برابر طول کوتاه ترین مسیر اقلیدسی بر فراز یک زمین است در زمان (فرمول در متن مقاله ) محاسبه می کند حافظه ی مورد نیاز هر دو الگوریتم از مرتبه O(n است.

Keywords:

هندسه ی محاسباتی , الگوریتم تقریبی , کوتاه ترین مسیر , زمین چند وجهی