موضوع مقاله: کره محیطی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کره محیطی | مقدمه: در ریاضیات، برای هر مجموعهٔ ناتهی از اشیایی که در یک فضای n-بعدی هستند، به‌طور مثال مجموعه‌ای از نقاط، یک کرهٔ محیطی برای آن مجموعه، یک کرهٔ توپر n-بعدی است که همه آن اشیا را در بر می‌گیرد. | ## بخش 1: کره محیطی | در علوم هندسهٔ محاسباتی و گرافیک کامپیوتری، یک کرهٔ محیطی نوع خاصی از حجم محیطی است. اثبات یکتا بودن این کره به این صورت است: فرض می‌کنیم دو کرهٔ محیطی حداقلی ولی متفاوت موجود باشد، اشیا مورد بحث باید در محدودهٔ مشترک این دو قرار داشته باشند؛ ولی می‌توان کره‌ای با شعاع کمتر طوری انتخاب کرد که ناحیهٔ مشترک آن دو را کاملاً دربرگیرد. مسئلهٔ یافتن مرکز کرهٔ محیطی حداقلی با نام «مسئله ۱-مرکز اقلیدسی بدون وزن» شناخته می‌شود. کاربردها خوشه‌بندی در خوشه‌بندی، هنگامی که گروهی از نقاط داده‌ای مشابه با یکدیگر دسته‌بندی شده باشند، از این کره‌ها استفاده می‌شود. در تحلیل‌های آماری شاخص‌های پراکندگی نقاط داده‌ای در یک کره، به خطای اندازه‌گیری یا به فرآیندهای طبیعی (معمولا فرآیندهای حرارتی) نسبت داده می‌شود، که در این حالت خوشه نمایانگر یک انحراف از یک نقطهٔ ایده‌آل است. در بعضی شرایط این نقطهٔ ایده‌آل به عنوان جایگزینی برای نقاط خوشه استفاده می‌شود تا زمان محاسبات کاهش یابد. در تحقیق در عملیات، خوشه‌بندی چند مقدار مختلف، در قالب یک نقطهٔ ایده‌آل، برای کاهش تعداد ورودی‌ها به منظور دستیابی به مقادیر تقریبی در مسائل NP-hard در زمان مناسب، استفاده می‌شود. نقطهٔ انتخاب شده معمولاً در وسط کره نیست، بلکه می‌تواند به سمت نقاط دورافتاده متمایل شود، ولی در عوض برخی اشکال دیگر محاسبهٔ مکان میانگین، مانند روش کمترین مربعات، برای نمایش خوشه به کار می‌رود. الگوریتم‌ها برای حل کردن مسئلهٔ کرهٔ محیطی الگوریتم‌های دقیق و همچنین الگوریتم‌های تقریبی مختلفی وجود دارند. | ## بخش 2: کره محیطی | این الگوریتم به علت ساده بودن به طرز گسترده‌ای برای کاربردهای مختلف استفاده می‌شود. یک نقطه از P انتخاب کرده و آن را x می‌نامیم، نقطهٔ y را طوری از P انتخاب می‌کنیم که بیشترین فاصله را از x داشته باشد. کرهٔ B را طوری اختیار می‌کنیم که مرکز آن نقطهٔ وسط y و z و شعاع آن نصف فاصلهٔ بین y و z باشد. اگر همهٔ نقاط مجموعهٔ P در کرهٔ B باشند، در این صورت یک کرهٔ محیطی پیدا کرده‌ایم. در غیر این صورت، یکی از نقاط خارج از کرهٔ B را انتخاب کرده آن را p می‌نامیم و یک کرهٔ جدید را طوری اختیار می‌کنیم که نقطهٔ p و کرهٔ قبلی را دربرگیرد. وقتی که بُعد وارد محاسبات می‌شود پیچیدگی زمان اجرا می‌باشد، گرچه در کاربردهای با ابعاد بالا، عملی نیست. در سال ۱۹۹۱ ایمو ولزی الگوریتم تصادفی بسیار ساده‌تری را بر اساس تعمیم الگوریتم تصادفی برنامه‌ریزی خطی سایدل، ارائه داد. تخمین براساس مجموعهٔ هسته بادویو و همکارانش برای مسئلهٔ کرهٔ محیطی یک تقریب ارائه دادند.M. منظور از تقریب این است که اگر کره‌ای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کره‌ای با شعاع وجود دارد که همهٔ نقاط را پوشش می‌دهد. | ## بخش 3: کره محیطی | «مجموعهٔ هسته» زیرمجموعهٔ کوچکی است که یک بسط از راه حل روی آن زیر مجموعه یک کرهٔ محیطی از تمام مجموعه است. مجموعهٔ هسته به تدریج و طی چند مرحله ایجاد می‌شود که در هر مرجله دورترین نقطهٔ مجموعه اضافه می‌گردد. حل‌کنندهٔ دقیق فیشر فیشر و همکارانش یک راه حل دقیق برای مسئلهٔ کرهٔ محیطی حداقلی ارائه دادند.K. 630-641, 2003 این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر می‌گیرد شروع می‌شود و سپس به تدریج آن‌قدر کوچک می‌شود تا به جایی برسد که کوچک‌تر شدن ممکن نباشد. این الگوریتم در زمان اجرا می‌شود و تا به حال سریع‌ترین راه حل دقیق شناخته شده برای این مسئله است. یک پیاده‌سازی به زبان برای این الگوریتم به عنوان یک پروژهٔ متن باز در دسترس است. ساده‌ترین نوع آن در زمان با خطای حدود یک جایگزین مناسب برای الگوریتم ریتر می‌باشد. یک تخمین ساده که در زمان اجرا می‌شود برای کاربردهای با دقت کمتر (برای ε>۱۰−۳) توصیه می‌شود، و یک تخمین دیگر که در زمان اجرا می‌شود برای کاربردهای با دقت بالاتر توصیه می‌شود. ایدهٔ اصلی این الگوریتم ساده است: هربار یک نقطهٔ بیرون از کره را پیدا کرده و سپس کره را به سمت آن نقطه حرکت داده و به‌طور هم‌زمان شعاع آن را زیاد می‌کنیم. | ## جمع‌بندی | میزان رشد در هر مرحله طوری طراحی شده‌است، که از شعاع بهینه تجاوز نمی‌کند، در نتیجه شعاع به حالت بهینه نزدیک و نزدیک‌تر می‌شود.