کره محیطی
در ریاضیات، برای هر مجموعهٔ ناتهی از اشیایی که در یک فضای n-بعدی هستند، بهطور مثال مجموعهای از نقاط، یک کرهٔ محیطی برای آن مجموعه، یک کرهٔ توپر n-بعدی است که همه آن اشیا را در بر میگیرد.
اگر فضای مورد نظر صفحه باشد، اصطلاحاً عبارت دایرهٔ محیطی به کار میرود.
در علوم هندسهٔ محاسباتی و گرافیک کامپیوتری، یک کرهٔ محیطی نوع خاصی از حجم محیطی است. برای ساختن یک کرهٔ محیطی چندین الگوریتم ساده و سریع با ارزش کاربردی بالا در برنامههای بیدرنگ(به انگلیسی: real-time) گرافیک کامپیوتری وجود دارد.[۱]
در علم آمار و تحقیق در عملیات، اشیا عمدتاً نقاط هستند، و کرهٔ مورد بحث عموماً کرهٔ محیطی حداقلی (به انگلیسی: minimal bounding sphere) است. کرهٔ محیطی حداقلی کرهای است که در بین همهٔ کرههای محیطی شعاع حداقلی دارد. اثبات یکتا بودن این کره به این صورت است: فرض میکنیم دو کرهٔ محیطی حداقلی ولی متفاوت موجود باشد، اشیا مورد بحث باید در محدودهٔ مشترک این دو قرار داشته باشند؛ ولی میتوان کرهای با شعاع کمتر طوری انتخاب کرد که ناحیهٔ مشترک آن دو را کاملاً دربرگیرد. پس آن دو کرهٔ قبلی حداقلی نبودهاند. پس طبق برهان خلف نتیجه میگیریم که کرهٔ محیطی آن نقاط، یکتا است.
مسئلهٔ یافتن مرکز کرهٔ محیطی حداقلی با نام «مسئله ۱-مرکز اقلیدسی بدون وزن»(به انگلیسی: unweighted Euclidean 1-center problem) شناخته میشود.
کاربردها
خوشهبندی
در خوشهبندی(به انگلیسی: clustering)، هنگامی که گروهی از نقاط دادهای مشابه با یکدیگر دستهبندی شده باشند، از این کرهها استفاده میشود.
در تحلیلهای آماری شاخصهای پراکندگی نقاط دادهای در یک کره، به خطای اندازهگیری یا به فرآیندهای طبیعی (معمولا فرآیندهای حرارتی) نسبت داده میشود، که در این حالت خوشه نمایانگر یک انحراف از یک نقطهٔ ایدهآل است. در بعضی شرایط این نقطهٔ ایدهآل به عنوان جایگزینی برای نقاط خوشه استفاده میشود تا زمان محاسبات کاهش یابد.
در تحقیق در عملیات، خوشهبندی چند مقدار مختلف، در قالب یک نقطهٔ ایدهآل، برای کاهش تعداد ورودیها به منظور دستیابی به مقادیر تقریبی در مسائل NP-hard در زمان مناسب، استفاده میشود. نقطهٔ انتخاب شده معمولاً در وسط کره نیست، بلکه میتواند به سمت نقاط دورافتاده متمایل شود، ولی در عوض برخی اشکال دیگر محاسبهٔ مکان میانگین، مانند روش کمترین مربعات، برای نمایش خوشه به کار میرود.
الگوریتمها
برای حل کردن مسئلهٔ کرهٔ محیطی الگوریتمهای دقیق و همچنین الگوریتمهای تقریبی مختلفی وجود دارند.
کرهٔ محیطی ریتر
جک ریتر(به انگلیسی: Jack Ritter) یک الگوریتم ساده برای یافتن کرهٔ محیطی ارائه داد.[۲] این الگوریتم به علت ساده بودن به طرز گستردهای برای کاربردهای مختلف استفاده میشود. این الگوریتم به شکل زیر عمل میکند:
(فرض میکنیم P مجموعه نقاط دادهای باشد)
۱. یک نقطه از P انتخاب کرده و آن را x مینامیم، نقطهٔ y را طوری از P انتخاب میکنیم که بیشترین فاصله را از x داشته باشد.
۲. نقطهٔ z را از P طوری انتخاب میکنیم که بیشترین فاصله را از y داشته باشد. کرهٔ B را طوری اختیار میکنیم که مرکز آن نقطهٔ وسط y و z و شعاع آن نصف فاصلهٔ بین y و z باشد.
۳. اگر همهٔ نقاط مجموعهٔ P در کرهٔ B باشند، در این صورت یک کرهٔ محیطی پیدا کردهایم. در غیر این صورت، یکی از نقاط خارج از کرهٔ B را انتخاب کرده آن را p مینامیم و یک کرهٔ جدید را طوری اختیار میکنیم که نقطهٔ p و کرهٔ قبلی را دربرگیرد. این کار را آنقدر تکرار میکنیم تا همهٔ نقاط را پوشش دهیم.
واضح است که الگوریتم ریتر در زمان اجرا میشود که بسیار کاراست. این روش جوابی را میدهد که معمولاً فقط حدود ۵ تا ۲۰ درصد از جواب بهینه بزرگتر است.[۳]
برنامهریزی خطی
در سال ۱۹۸۳ نیمراد مگیدو(به انگلیسی: Nimrod Megiddo) یک الگوریتم «هرس و جستجو»(به انگلیسی: prune and search) ارائه داد که اگر بُعد آن ثابت باشد، در زمان خطی اجرا میشود. وقتی که بُعد وارد محاسبات میشود پیچیدگی زمان اجرا میباشد، گرچه در کاربردهای با ابعاد بالا، عملی نیست. مگیدو از این روش برای حل برنامهریزی خطی در زمان خطی با بُعد ثابت استفاده کرد.
در سال ۱۹۹۱ ایمو ولزی(به انگلیسی: Emo Welzl) الگوریتم تصادفی بسیار سادهتری را بر اساس تعمیم الگوریتم تصادفی برنامهریزی خطی سایدل، ارائه داد. این الگوریتم در زمان خطی مورد نظر اجرا میشود و نتایج اجرای آن نشان میدهد که برای ابعاد بالاتر نیز کارایی دارد.[۴]
کتابخانهٔ متن-باز الگوریتمهای هندسهٔ محاسباتی(به انگلیسی: Computational Geometry Algorithms Library) پیادهسازی این الگوریتم را دارد.
تخمین ۱+ε براساس مجموعهٔ هسته
بادویو(به رومانیایی: Bădoiu) و همکارانش برای مسئلهٔ کرهٔ محیطی یک تقریب ارائه دادند.[۵] منظور از تقریب این است که اگر کرهای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کرهای با شعاع وجود دارد که همهٔ نقاط را پوشش میدهد.
«مجموعهٔ هسته»(به انگلیسی: Core set) زیرمجموعهٔ کوچکی است که یک بسط از راه حل روی آن زیر مجموعه یک کرهٔ محیطی از تمام مجموعه است. مجموعهٔ هسته به تدریج و طی چند مرحله ایجاد میشود که در هر مرجله دورترین نقطهٔ مجموعه اضافه میگردد.
کومار(به انگلیسی: Kumar) و همکارانش این الگوریتم تخمینی را بهبود دادند،[۶] بهطوریکه در زمان اجرا شود.
حلکنندهٔ دقیق فیشر
فیشر(به انگلیسی: Fischer) و همکارانش یک راه حل دقیق برای مسئلهٔ کرهٔ محیطی حداقلی ارائه دادند.[۷] این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر میگیرد شروع میشود و سپس به تدریج آنقدر کوچک میشود تا به جایی برسد که کوچکتر شدن ممکن نباشد.
این الگوریتم در زمان اجرا میشود و تا به حال سریعترین راه حل دقیق شناخته شده برای این مسئله است. در عمل، این الگوریتم برای بعدهای کم (حداکثر ۱۰۰۰۰ بعد) بسیار کارا است. یک پیادهسازی به زبان C++ برای این الگوریتم به عنوان یک پروژهٔ متن باز در دسترس است.
حباب ارتجاعی
حباب ارتجاعی یک الگوریتم تخمینی برای مسئلهٔ کرهٔ محیطی حداقلی است.[۳] این الگوریتم انواع مختلفی برای اهداف متفاوت دارد. سادهترین نوع آن در زمان با خطای حدود ۱٪~%۲ یک جایگزین مناسب برای الگوریتم ریتر میباشد. یک تخمین ساده که در زمان اجرا میشود برای کاربردهای با دقت کمتر (برای ε>۱۰−۳) توصیه میشود، و یک تخمین دیگر که در زمان اجرا میشود برای کاربردهای با دقت بالاتر توصیه میشود.
ایدهٔ اصلی این الگوریتم ساده است: هربار یک نقطهٔ بیرون از کره را پیدا کرده و سپس کره را به سمت آن نقطه حرکت داده و بهطور همزمان شعاع آن را زیاد میکنیم. میزان رشد در هر مرحله طوری طراحی شدهاست، که از شعاع بهینه تجاوز نمیکند، در نتیجه شعاع به حالت بهینه نزدیک و نزدیکتر میشود.
انیمیشن زیر فرایند نوع اول را نمایش میدهد:
جستارهای وابسته
- حجم محیطی
- مسئلهٔ کوچکترین دایره
منابع
- ↑ Fast and Tight Fitting Bounding Spheres
- ↑ J. Ritter. An efficient bounding sphere. In Andrew S. Glassner, editor, Graphics Gems. Academic Press, Boston, MA, 1990.
- ↑ ۳٫۰ ۳٫۱ 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.
- ↑ 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 بایگانیشده در ۱۲ دسامبر ۲۰۱۳ توسط Wayback Machine, Proc. 11th European Symposium on Algorithms (ESA), p. 630-641, 2003
پیوند به بیرون
- مسئلهٔ کوچکترین دایره محصورکننده – چند الگوریتم برای محصور کردن مجموعهای از نقاط را توضیح میدهد، که شامل الگوریتم با زمان اجرای خطّی مگیدو نیز میباشد.