انجمن کامپیوتر ایران

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