کره محیطی
در ریاضیات، برای هر مجموعهٔ ناتهی از اشیایی که در یک فضای "n"-بعدی هستند، به‌طور مثال مجموعه‌ای از نقاط، یک کرهٔ محیطی برای آن مجموعه، یک کرهٔ توپر "n"-بعدی است که همه آن اشیا را در بر می‌گیرد.
اگر فضای مورد نظر صفحه باشد، اصطلاحاً عبارت دایرهٔ محیطی به کار می‌رود.
در علوم هندسهٔ محاسباتی و گرافیک کامپیوتری، یک کرهٔ محیطی نوع خاصی از حجم محیطی است. برای ساختن یک کرهٔ محیطی چندین الگوریتم ساده و سریع با ارزش کاربردی بالا در برنامه‌های بی‌درنگ گرافیک کامپیوتری وجود دارد.
در علم آمار و تحقیق در عملیات، اشیا عمدتاً نقاط هستند، و کرهٔ مورد بحث عموماً کرهٔ محیطی حداقلی است. کرهٔ محیطی حداقلی کره‌ای است که در بین همهٔ کره‌های محیطی شعاع حداقلی دارد. اثبات یکتا بودن این کره به این صورت است: فرض می‌کنیم دو کرهٔ محیطی حداقلی ولی متفاوت موجود باشد، اشیا مورد بحث باید در محدودهٔ مشترک این دو قرار داشته باشند؛ ولی می‌توان کره‌ای با شعاع کمتر طوری انتخاب کرد که ناحیهٔ مشترک آن دو را کاملاً دربرگیرد. پس آن دو کرهٔ قبلی حداقلی نبوده‌اند. پس طبق برهان خلف نتیجه می‌گیریم که کرهٔ محیطی آن نقاط، یکتا است.
مسئلهٔ یافتن مرکز کرهٔ محیطی حداقلی با نام «مسئله ۱-مرکز اقلیدسی بدون وزن» شناخته می‌شود.
در خوشه‌بندی، هنگامی که گروهی از نقاط داده‌ای مشابه با یکدیگر دسته‌بندی شده باشند، از این کره‌ها استفاده می‌شود.
در تحلیل‌های آماری شاخص‌های پراکندگی نقاط داده‌ای در یک کره، به خطای اندازه‌گیری یا به فرآیندهای طبیعی (معمولا فرآیندهای حرارتی) نسبت داده می‌شود، که در این حالت خوشه نمایانگر یک انحراف از یک نقطهٔ ایده‌آل است. در بعضی شرایط این نقطهٔ ایده‌آل به عنوان جایگزینی برای نقاط خوشه استفاده می‌شود تا زمان محاسبات کاهش یابد.
در تحقیق در عملیات، خوشه‌بندی چند مقدار مختلف، در قالب یک نقطهٔ ایده‌آل، برای کاهش تعداد ورودی‌ها به منظور دستیابی به مقادیر تقریبی در مسائل NP-hard در زمان مناسب، استفاده می‌شود. نقطهٔ انتخاب شده معمولاً در وسط کره نیست، بلکه می‌تواند به سمت نقاط دورافتاده متمایل شود، ولی در عوض برخی اشکال دیگر محاسبهٔ مکان میانگین، مانند روش کمترین مربعات، برای نمایش خوشه به کار می‌رود.
برای حل کردن مسئلهٔ کرهٔ محیطی الگوریتم‌های دقیق و همچنین الگوریتم‌های تقریبی مختلفی وجود دارند.
جک ریتر یک الگوریتم ساده برای یافتن کرهٔ محیطی ارائه داد. این الگوریتم به علت ساده بودن به طرز گسترده‌ای برای کاربردهای مختلف استفاده می‌شود. این الگوریتم به شکل زیر عمل می‌کند:
۱. یک نقطه از P انتخاب کرده و آن را x می‌نامیم، نقطهٔ y را طوری از P انتخاب می‌کنیم که بیشترین فاصله را از x داشته باشد.
۲. نقطهٔ z را از P طوری انتخاب می‌کنیم که بیشترین فاصله را از y داشته باشد. کرهٔ B را طوری اختیار می‌کنیم که مرکز آن نقطهٔ وسط y و z و شعاع آن نصف فاصلهٔ بین y و z باشد.
۳. اگر همهٔ نقاط مجموعهٔ P در کرهٔ B باشند، در این صورت یک کرهٔ محیطی پیدا کرده‌ایم. در غیر این صورت، یکی از نقاط خارج از کرهٔ B را انتخاب کرده آن را p می‌نامیم و یک کرهٔ جدید را طوری اختیار می‌کنیم که نقطهٔ p و کرهٔ قبلی را دربرگیرد. این کار را آن‌قدر تکرار می‌کنیم تا همهٔ نقاط را پوشش دهیم.
واضح است که الگوریتم ریتر در زمان formula_1 اجرا می‌شود که بسیار کاراست. این روش جوابی را می‌دهد که معمولاً فقط حدود ۵ تا ۲۰ درصد از جواب بهینه بزرگتر است.
در سال ۱۹۸۳ نیمراد مگیدو یک الگوریتم «هرس و جستجو» ارائه داد که اگر بُعد آن ثابت باشد، در زمان خطی اجرا می‌شود. وقتی که بُعد وارد محاسبات می‌شود پیچیدگی زمان اجرا formula_2 می‌باشد، گرچه در کاربردهای با ابعاد بالا، عملی نیست. مگیدو از این روش برای حل برنامه‌ریزی خطی در زمان خطی با بُعد ثابت استفاده کرد.
در سال ۱۹۹۱ ایمو ولزی الگوریتم تصادفی بسیار ساده‌تری را بر اساس تعمیم الگوریتم تصادفی برنامه‌ریزی خطی سایدل، ارائه داد. این الگوریتم در زمان خطی مورد نظر اجرا می‌شود و نتایج اجرای آن نشان می‌دهد که برای ابعاد بالاتر نیز کارایی دارد.
بادویو و همکارانش برای مسئلهٔ کرهٔ محیطی یک تقریب formula_3 ارائه دادند. منظور از تقریب formula_3 این است که اگر کره‌ای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کره‌ای با شعاع formula_5 وجود دارد که همهٔ نقاط را پوشش می‌دهد.
«مجموعهٔ هسته» زیرمجموعهٔ کوچکی است که یک بسط formula_3 از راه حل روی آن زیر مجموعه یک کرهٔ محیطی از تمام مجموعه است. مجموعهٔ هسته به تدریج و طی چند مرحله ایجاد می‌شود که در هر مرجله دورترین نقطهٔ مجموعه اضافه می‌گردد.
کومار و همکارانش این الگوریتم تخمینی را بهبود دادند، به‌طوری‌که در زمان formula_7 اجرا شود.
فیشر و همکارانش یک راه حل دقیق برای مسئلهٔ کرهٔ محیطی حداقلی ارائه دادند. این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر می‌گیرد شروع می‌شود و سپس به تدریج آن‌قدر کوچک می‌شود تا به جایی برسد که کوچک‌تر شدن ممکن نباشد.
این الگوریتم در زمان formula_8 اجرا می‌شود و تا به حال سریع‌ترین راه حل دقیق شناخته شده برای این مسئله است. در عمل، این الگوریتم برای بعدهای کم (حداکثر ۱۰۰۰۰ بعد) بسیار کارا است. یک پیاده‌سازی به زبان برای این الگوریتم به عنوان یک پروژهٔ متن باز در دسترس است.
حباب ارتجاعی یک الگوریتم تخمینی برای مسئلهٔ کرهٔ محیطی حداقلی است. این الگوریتم انواع مختلفی برای اهداف متفاوت دارد. ساده‌ترین نوع آن در زمان formula_1 با خطای حدود یک جایگزین مناسب برای الگوریتم ریتر می‌باشد. یک تخمین formula_3 ساده که در زمان formula_11 اجرا می‌شود برای کاربردهای با دقت کمتر (برای ε>۱۰) توصیه می‌شود، و یک تخمین formula_3 دیگر که در زمان formula_13 اجرا می‌شود برای کاربردهای با دقت بالاتر توصیه می‌شود.
ایدهٔ اصلی این الگوریتم ساده است: هربار یک نقطهٔ بیرون از کره را پیدا کرده و سپس کره را به سمت آن نقطه حرکت داده و به‌طور هم‌زمان شعاع آن را زیاد می‌کنیم. میزان رشد در هر مرحله طوری طراحی شده‌است، که از شعاع بهینه تجاوز نمی‌کند، در نتیجه شعاع به حالت بهینه نزدیک و نزدیک‌تر می‌شود.
انیمیشن زیر فرایند نوع اول را نمایش می‌دهد: