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

مسئله درخت اشتاینر منجر به راه حل هایی در زمینه علمی و تجاری مختلف شده است که مسیر یابی شبکه های کامپیوتری و مدارهای مجتمع الکترونیکی از آن جمله هستند . زمینه های محاسباتی این مسئله ،آن راتبدیل به یک موضوع مهم تحقیقاتی در هندسه محاسباتی کرده است . با در نظر گرفتن چند نقطه در صفحه اقلیدسی که به این نقاط ترمینال گویند یک درخت پوشای مینیمم بدست می آید که این نقاط را به هم متصلمی کند به این درخت یکسری نقاط دیگر (نقاط اشتاینر ) اضافه می شود که باعث کوتاهتر شدن طول درخت می شود که به درخت حاصل ،درخت اشتاینر کمینه اقلیدسی می گویند . این مسئله به عنوان مسئلهNP_hard در نظر گرفته می شود. با در نظر گرفتن چند ضلعی ساده p با m راس وn ترمینال درآن سعی می گردد یک درخت کمینه اشتاینر اقلیدسی پیدا شود که به همهn ترمینال موجود درp متصل باشد. در این مقاله ما راه حلی برای چند ترمینال در یک چند ضلعی ساده با وجود موانع پیشنهاد کر ده ایم

Keywords:

درخت اشتاینر , درخت اشتاینر کمینه اقلیدسی , مثلث بندی دلونوی , چند ضلعی ساده