کره محیطی

در ریاضیات، برای هر مجموعهٔ ناتهی از اشیایی که در یک فضای *n*-بعدی هستند، به‌طور مثال مجموعه‌ای از نقاط، یک **کرهٔ محیطی** برای آن مجموعه، یک کرهٔ توپر *n*-بعدی است که همه آن اشیا را در بر می‌گیرد.

اگر فضای مورد نظر صفحه باشد، اصطلاحاً عبارت **دایرهٔ محیطی** به کار می‌رود.

در علوم هندسهٔ محاسباتی و گرافیک کامپیوتری، یک کرهٔ محیطی نوع خاصی از حجم محیطی است. برای ساختن یک کرهٔ محیطی چندین الگوریتم ساده و سریع با ارزش کاربردی بالا در برنامه‌های بی‌درنگ گرافیک  کامپیوتری وجود دارد.

در علم آمار و تحقیق در عملیات، اشیا عمدتاً نقاط هستند، و کرهٔ مورد بحث عموماً **کرهٔ محیطی حداقلی**  است. کرهٔ محیطی حداقلی کره‌ای است که در بین همهٔ کره‌های محیطی شعاع حداقلی دارد. اثبات یکتا بودن این کره به این صورت است:
فرض می‌کنیم دو کرهٔ محیطی حداقلی ولی متفاوت موجود باشد، اشیا مورد بحث باید در محدودهٔ مشترک این دو قرار داشته باشند؛ ولی می‌توان کره‌ای با شعاع کمتر طوری انتخاب کرد که ناحیهٔ مشترک آن دو را کاملاً دربرگیرد. پس آن دو کرهٔ قبلی حداقلی نبوده‌اند. پس طبق برهان خلف نتیجه می‌گیریم که کرهٔ محیطی آن نقاط، یکتا است.

مسئلهٔ یافتن مرکز کرهٔ محیطی حداقلی با نام «مسئله ۱-مرکز اقلیدسی بدون وزن» شناخته می‌شود.

## کاربردها
### خوشه‌بندی
در خوشه‌بندی، هنگامی که گروهی از نقاط داده‌ای مشابه با یکدیگر دسته‌بندی شده باشند، از این کره‌ها استفاده می‌شود.

در تحلیل‌های آماری شاخص‌های پراکندگی نقاط داده‌ای در یک کره، به خطای اندازه‌گیری یا به فرآیندهای طبیعی (معمولا فرآیندهای حرارتی) نسبت داده می‌شود، که در این حالت خوشه نمایانگر یک انحراف از یک نقطهٔ ایده‌آل است. در بعضی شرایط این نقطهٔ ایده‌آل به عنوان جایگزینی برای نقاط خوشه استفاده می‌شود تا زمان محاسبات کاهش یابد.

در تحقیق در عملیات، خوشه‌بندی چند مقدار مختلف، در قالب یک نقطهٔ ایده‌آل، برای کاهش تعداد ورودی‌ها به منظور دستیابی به مقادیر تقریبی در مسائل NP-hard در زمان مناسب، استفاده می‌شود. نقطهٔ انتخاب شده معمولاً در وسط کره نیست، بلکه می‌تواند به سمت نقاط دورافتاده متمایل شود، ولی در عوض برخی اشکال دیگر محاسبهٔ مکان میانگین، مانند روش کمترین مربعات، برای نمایش خوشه به کار می‌رود.

## الگوریتم‌ها
برای حل کردن مسئلهٔ کرهٔ محیطی الگوریتم‌های دقیق و همچنین الگوریتم‌های تقریبی مختلفی وجود دارند.

### کرهٔ محیطی ریتر
جک ریتر یک الگوریتم ساده برای یافتن کرهٔ محیطی ارائه داد.
این الگوریتم به علت ساده بودن به طرز گسترده‌ای برای کاربردهای مختلف استفاده می‌شود. این الگوریتم به شکل زیر عمل می‌کند:

(فرض می‌کنیم P مجموعه نقاط داده‌ای باشد)

۱. یک نقطه از P انتخاب کرده و آن را x می‌نامیم، نقطهٔ y را طوری از P انتخاب می‌کنیم که بیشترین فاصله را از x داشته باشد.

۲. نقطهٔ z را از P طوری انتخاب می‌کنیم که بیشترین فاصله را از y داشته باشد. کرهٔ B را طوری اختیار می‌کنیم که مرکز آن نقطهٔ وسط y و z و شعاع آن نصف فاصلهٔ بین y و z باشد.

۳. اگر همهٔ نقاط مجموعهٔ P در کرهٔ B باشند، در این صورت یک کرهٔ محیطی پیدا کرده‌ایم. در غیر این صورت، یکی از نقاط خارج از کرهٔ B را انتخاب کرده آن را p می‌نامیم و یک کرهٔ جدید را طوری اختیار می‌کنیم که نقطهٔ p و کرهٔ قبلی را دربرگیرد. این کار را آن‌قدر تکرار می‌کنیم تا همهٔ نقاط را پوشش دهیم.

واضح است که الگوریتم ریتر در زمان O(nd)  اجرا می‌شود که بسیار کاراست. این روش جوابی را می‌دهد که معمولاً فقط حدود ۵ تا ۲۰ درصد از جواب بهینه بزرگتر است.

### برنامه‌ریزی خطی
در سال ۱۹۸۳ نیمراد مگیدو یک الگوریتم «هرس و جستجو» ارائه داد که اگر بُعد آن ثابت باشد، در زمان خطی اجرا می‌شود. وقتی که بُعد وارد محاسبات می‌شود پیچیدگی زمان اجرا O((d+1)(d+1)!\,n) می‌باشد، گرچه در کاربردهای با ابعاد بالا، عملی نیست. مگیدو از این روش برای حل برنامه‌ریزی خطی در زمان خطی با بُعد ثابت استفاده کرد.

در سال ۱۹۹۱ ایمو ولزی الگوریتم تصادفی بسیار ساده‌تری را بر اساس تعمیم الگوریتم تصادفی برنامه‌ریزی خطی سایدل، ارائه داد. این الگوریتم در زمان خطی مورد نظر اجرا می‌شود و نتایج اجرای آن نشان می‌دهد که برای ابعاد بالاتر نیز کارایی دارد.

کتابخانهٔ متن-باز الگوریتم‌های هندسهٔ محاسباتی پیاده‌سازی این الگوریتم را دارد.

### تخمین  براساس مجموعهٔ هسته
بادویو و همکارانش برای مسئلهٔ کرهٔ محیطی یک تقریب 1+\epsilon ارائه دادند.
منظور از تقریب 1+\epsilon این است که اگر کره‌ای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کره‌ای با شعاع (1+\epsilon)r وجود دارد که همهٔ نقاط را پوشش می‌دهد.

«مجموعهٔ هسته» زیرمجموعهٔ کوچکی است که یک بسط 1+\epsilon از راه حل روی آن زیر مجموعه یک کرهٔ محیطی از تمام مجموعه است. مجموعهٔ هسته به تدریج و طی چند مرحله ایجاد می‌شود که در هر مرجله دورترین نقطهٔ مجموعه اضافه می‌گردد.

کومار و همکارانش این الگوریتم تخمینی را بهبود دادند،
به‌طوری‌که در زمان O(\frac{nd}{\epsilon}+ \frac{1}{\epsilon^{4.5}}\log{\frac{1}{\epsilon}}) اجرا شود.

### حل‌کنندهٔ دقیق فیشر
فیشر و همکارانش یک راه حل دقیق برای مسئلهٔ کرهٔ محیطی حداقلی ارائه دادند.
این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر می‌گیرد شروع می‌شود و سپس به تدریج آن‌قدر کوچک می‌شود تا به جایی برسد که کوچک‌تر شدن ممکن نباشد.

این الگوریتم در زمان O(nd^2) اجرا می‌شود و تا به حال سریع‌ترین راه حل دقیق شناخته شده برای این مسئله است. در عمل، این الگوریتم برای بعدهای کم (حداکثر ۱۰۰۰۰ بعد) بسیار کارا است. یک پیاده‌سازی به زبان  برای این الگوریتم به عنوان یک پروژهٔ متن باز در دسترس است.

### حباب ارتجاعی
حباب ارتجاعی یک الگوریتم تخمینی برای مسئلهٔ کرهٔ محیطی حداقلی است.
این الگوریتم انواع مختلفی برای اهداف متفاوت دارد. ساده‌ترین نوع آن در زمان O(nd) با خطای حدود  یک جایگزین مناسب برای الگوریتم ریتر می‌باشد. یک تخمین 1+\epsilon ساده که در زمان O(\frac {nd}{\epsilon^2}) اجرا می‌شود برای کاربردهای با دقت کمتر (برای &epsilon;>۱۰−۳) توصیه می‌شود، و یک تخمین  1+\epsilon دیگر که در زمان O(nd)+O(\frac{d}{\epsilon^2}) اجرا می‌شود برای کاربردهای با دقت بالاتر توصیه می‌شود.

ایدهٔ اصلی این الگوریتم ساده است: هربار یک نقطهٔ بیرون از کره را پیدا کرده و سپس کره را به سمت آن نقطه حرکت داده و به‌طور هم‌زمان شعاع آن را زیاد می‌کنیم. میزان رشد در هر مرحله طوری طراحی شده‌است، که از شعاع بهینه تجاوز نمی‌کند، در نتیجه شعاع به حالت بهینه نزدیک و نزدیک‌تر می‌شود.

انیمیشن زیر فرایند نوع اول را نمایش می‌دهد:

## جستارهای وابسته
* حجم محیطی
* مسئلهٔ کوچکترین دایره

## منابع

## پیوند به بیرون
* مسئلهٔ کوچکترین دایره محصور‌کننده – چند الگوریتم برای محصور کردن مجموعه‌ای از نقاط را توضیح می‌دهد، که شامل الگوریتم با زمان اجرای خطّی مگیدو نیز می‌باشد.

رده:الگوریتم‌های هندسی
رده:کره‌ها (هندسه)