عنوان
حل مسئله (n, 1, 1, α)-مرکز در فضاي دو بعدي
نویسنده (گان)
کاوند,پرديس;اسکندري,مرضيه;محدث,علي
چکیده مقاله
مجموعه ي S شامل n نقطه در صفحه و ثابت α داده شده است. مسئله ي (n,1,1,α)-مرکز عبارت است از يافتن دو ديسک بسته در صفحه که هريک از آنها به تنهايي کل S را بپوشاند، با اين شرط که شعاع ديسک بزرگتر کمينه شود و فاصله ي مراکز آنها از يکديگر حداقل برابر با α باشد. مسئله ي (n,1,1,α)-مرکز مقيد نسخه اي از مسئله ي (n,1,1,α)-مرکز است که در آن مکان قرارگيري مراکز به خط داده شده اي محدود شده است. ما در اين مقاله مسئله ي (n,1,1,α)-مرکز و نسخه ي مقيد آن را معرفي مي کنيم سپس يک الگوريتم با پيچيدگي زماني ( O(n log n براي حل مسئله ي (n,1,1,α)-مرکز و يک الگوريتم خطي براي حل نسخه ي مقيد آن ارائه مي دهيم.

متن کامل مقاله