کره محیطی

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

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

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

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

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

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

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

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

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

 کرهٔ محیطی ریتر 
جک ریتر یک الگوریتم ساده برای یافتن کرهٔ محیطی ارائه داد.J. Ritter. An efficient bounding sphere. In Andrew S. Glassner, editor, Graphics Gems. Academic Press, Boston, MA, 1990.
این الگوریتم به علت ساده بودن به طرز گسترده‌ای برای کاربردهای مختلف استفاده می‌شود. این الگوریتم به شکل زیر عمل می‌کند:

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

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

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

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

واضح است که الگوریتم ریتر در زمان   اجرا می‌شود که بسیار کاراست. این روش جوابی را می‌دهد که معمولاً فقط حدود ۵ تا ۲۰ درصد از جواب بهینه بزرگتر است.Bo Tian, Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem 2012

 برنامه‌ریزی خطی 
در سال ۱۹۸۳ نیمراد مگیدو یک الگوریتم «هرس و جستجو» ارائه داد که اگر بُعد آن ثابت باشد، در زمان خطی اجرا می‌شود. وقتی که بُعد وارد محاسبات می‌شود پیچیدگی زمان اجرا  می‌باشد، گرچه در کاربردهای با ابعاد بالا، عملی نیست. مگیدو از این روش برای حل برنامه‌ریزی خطی در زمان خطی با بُعد ثابت استفاده کرد.

در سال ۱۹۹۱ ایمو ولزی الگوریتم تصادفی بسیار ساده‌تری را بر اساس تعمیم الگوریتم تصادفی برنامه‌ریزی خطی سایدل، ارائه داد. این الگوریتم در زمان خطی مورد نظر اجرا می‌شود و نتایج اجرای آن نشان می‌دهد که برای ابعاد بالاتر نیز کارایی دارد.Emo Welzl, Smallest enclosing disks (balls and ellipsoids), New Results and New Trends in Computer Science, Volume 555, 1991, pp 359–370

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

 تخمین  براساس مجموعهٔ هسته 
بادویو و همکارانش برای مسئلهٔ کرهٔ محیطی یک تقریب  ارائه دادند.M. Bădoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. Proc. 34th Annu. ACM Sympos.on Theory of Computing, pages 250–257, 2002.
منظور از تقریب  این است که اگر کره‌ای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کره‌ای با شعاع  وجود دارد که همهٔ نقاط را پوشش می‌دهد.

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

کومار و همکارانش این الگوریتم تخمینی را بهبود دادند،P. Kumar, J.S.B. Mitchell and E.A Yıldırım. Computing Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions, 2003
به‌طوری‌که در زمان  اجرا شود.

 حل‌کنندهٔ دقیق فیشر 
فیشر و همکارانش یک راه حل دقیق برای مسئلهٔ کرهٔ محیطی حداقلی ارائه دادند.K. Fischer, B. Gärtner and M. Kutz: Fast Smallest-Enclosing-Ball Computation in High Dimensions , Proc. 11th European Symposium on Algorithms (ESA), p. 630-641, 2003
این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر می‌گیرد شروع می‌شود و سپس به تدریج آن‌قدر کوچک می‌شود تا به جایی برسد که کوچک‌تر شدن ممکن نباشد.

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

 حباب ارتجاعی 
حباب ارتجاعی یک الگوریتم تخمینی برای مسئلهٔ کرهٔ محیطی حداقلی است.
این الگوریتم انواع مختلفی برای اهداف متفاوت دارد. ساده‌ترین نوع آن در زمان  با خطای حدود  یک جایگزین مناسب برای الگوریتم ریتر می‌باشد. یک تخمین  ساده که در زمان  اجرا می‌شود برای کاربردهای با دقت کمتر (برای ε>۱۰−۳) توصیه می‌شود، و یک تخمین   دیگر که در زمان  اجرا می‌شود برای کاربردهای با دقت بالاتر توصیه می‌شود.

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

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

Animation of Bouncing Bubble algorithm

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

 منابع 

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

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