چکیده: در این پایان نامه با گراف رؤیت پذیری آشنا خواهیم شد که برای محاسبه طول کوتاهترین مسیر بین دو نقطه در فضای آزاد بین موانع مورد استفاده قرار می‌گیرد. سپس انواع مختلف کوتاهترین مسیر هندسی را در داخل یک چندضلعی ساده، که در آن اجازه داریم بخشی از مسیر به خارج از چندضلعی برود، مطالعه می‌کنیم. فرض کنید P یک چندضلعی ساده باشد که از n رأس تشکیل شده باشد و فرض کنید s و t دو نقطه در P باشند. برای یک عدد صحیح k≥0، یک مسیر k-حذفی از s به t مسیری است که s و t را به هم وصل کند به طوری که تقاطع آن با فضای بیرونی P حداکثر k پاره‌خط است. از نظر تعداد پاره‌خط‌های مسیر در داخل P، هیچ محدودیتی وجود ندارد. هدف این است که مسیری با حداقل طول اقلیدسی در بین تمام مسیرهای (k=>)-حذفی ممکن از s تا t محاسبه شود. در این پایان نامه، این مسئله را برای k=1 مطالعه می‌کنیم و الگوریتمی را پیشنهاد می‌کنیم که کوتاهترین مسیر یک-حذفی را در زمان (O(n^3 محاسبه می‌کند. نشان می‌دهیم که برای چندضلعی‌های مستطیل، حداقل طول مسیر یک-حذفی می‌تواند در زمان (O(n log⁡n محاسبه شود. همینطور طریقه یافتن نقشه کوتاهترین مسیر در میان h مانع محدب را بررسی می‌کنیم، طوریکه اجازه حذف حداکثر k مانع را داشته باشیم، برای k≤h. با توجه به نقطه ثابت داده شده s، نحوه ساخت یک نقشه را با نام کوتاهترین k-مسیر نشان می‌دهیم، بطوریکه همه مقصدها در ناحیه‌ای از نقشه، دارای یک کوتاهترین مسیر‌ ترکیبیاتی یکسان را که از بین حداکثر k مانع عبور خواهند کرد، هستند. محدودیت (θ(kn را برای اندازه این نقشه اثبات می‌کنیم که می‌تواند در مدت زمان (O(k^2 n log⁡n محاسبه شود، که در آن n تعداد کل رئوس موانع است.