کرهٔ محیطی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات، برای هر مجموعهٔ ناتهی از اشیایی که در یک فضای 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 و کرهٔ قبلی را در برگیرد. این کار را آن‌قدر تکرار می‌کنیم تا همهٔ نقاط را پوشش دهیم.

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

برنامه‌ریزی خطی[ویرایش]

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

در سال ۱۹۹۱ ایمو ولزی(به انگلیسی: Emo Welzl) الگوریتم تصادفی بسیار ساده‌تری را بر اساس تعمیم الگوریتم تصادفی برنامه‌ریزی خطی سایدل، ارائه داد. این الگوریتم در زمان خطی مورد نظر اجرا می‌شود و نتایج اجرای آن نشان می‌دهد که برای ابعاد بالاتر نیز کارایی دارد.[۴]

کتابخانهٔ متن-باز الگوریتم‌های هندسهٔ محاسباتی(به انگلیسی: Computational Geometry Algorithms Library) پیاده‌سازی این الگوریتم را دارد.

تخمین ۱+ε براساس مجموعهٔ هسته[ویرایش]

بادویو(به رومانیایی: Bădoiu) و همکارانش برای مسالهٔ کرهٔ محیطی یک تقریب 1+\epsilon ارائه دادند.[۵] منظور از تقریب 1+\epsilon این است که اگر کره‌ای با شعاع r همهٔ نقاط مجموعه را پوشش ندهد، کره‌ای با شعاع (1+\epsilon)r وجود دارد که همهٔ نقاط را پوشش می‌دهد.

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

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

حل کنندهٔ دقیق فیشر[ویرایش]

فیشر(به انگلیسی: Fischer) و همکارانش یک راه حل دقیق برای مسالهٔ کرهٔ محیطی حداقلی ارائه دادند.[۷] این الگوریتم با یک کرهٔ بزرگ که همهٔ نقاط را در بر می‌گیرد شروع می‌شود و سپس به تدریج آن‌قدر کوچک می‌شود تا به جایی برسد که کوچک‌تر شدن ممکن نباشد.

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

حباب ارتجاعی[ویرایش]

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

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

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

Animation of Bouncing Bubble algorithm

همچنین ببینید[ویرایش]

منابع[ویرایش]

  1. Fast and Tight Fitting Bounding Spheres
  2. J. Ritter. An efficient bounding sphere. In Andrew S. Glassner, editor, Graphics Gems. Academic Press, Boston, MA, 1990.
  3. ۳٫۰ ۳٫۱ Bo Tian, Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem 2012
  4. Emo Welzl, Smallest enclosing disks (balls and ellipsoids), New Results and New Trends in Computer Science, Volume 555, 1991, pp 359–370
  5. 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.
  6. 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
  7. 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

پیوند به بیرون[ویرایش]