تعیین نزدیکترین زوج نقاط در فضای دو بعدی
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
مسئله نزدیکترین زوج نقاط یا نزدیکترین زوج یک مسئله از هندسه محاسباتی است که در آن در فضای متری n نقطه به عنوان ورودی گرفته میشود و زوج نقطهای که کوتاهترین فاصله بین آندو وجود دارد، پیدا میشود. مسئله نزدیکترین زوج برای نقاط در صفحهٔ اقلیدسی[۱] از اولین مسائل هندسه بود که مطالعات سیستماتیک در نظریه پیچیدگی محاسباتی، الگوریتمهای هندسه شد.
الگوریتم ساده، پیدا کردن فاصلهٔ همهٔ زوج نقاط و انتخاب کمینهٔ آنهاست که نیازمند زمانی از مرتبهٔ O(n2) است. به نظر میرسد مسئله در زمان O(n log n) درفضای اقلیدسی یا Lp space با بعد ثابت d قابل حل باشد. در [�] [�] الگوریتم با زمان O(n log n) بهینه است. این بهینه بودن از این که [�] (با حد پائینO(n log n) برای پیچیدگی زمانی) قابل کاهش به مسئلهٔ نزدیکرین زوج است پیروی میکند: بررسی اینکه کمینهٔ فاصله صفر است یا خیر، پس از حل مسئله نزدیکترین زوج آیا دو نقطه منطبق برهم وجود دارند یا خیر.
در مدل محاسباتیای که در نظر میگیریم که [�] که در زمان ثابت قابل محاسبه است باعث حل مسئله در زمان O(n log n) میشود.[۲] اگر در تابع سقف از حالت تصادفی استفاده کنیم مسئله در زمان خطی قابل حل است.[۳][۴]
جستجوی جامع[ویرایش]
نزدیکترین زوج از نقاط با استتفاده از جستجوی جامع در نظریه پیچیدگی محاسباتی O(n2) قابل محاسبه است. برای این کار باید فاصلهٔ میان تمام n(n − ۱) / ۲ زوج نقطه را محاسبه کرده و زوجی را که کمترین فاصله را دارند، برگزینیم. شبه کد این الگوریتم در زیرمشاهده میشود.[۱]
minDist = infinity for i = 1 to length(P) - ۱ for j = i + 1 to length(P) let p = P[i], q = P[j] if dist(p, q) <minDist: minDist = dist(p, q) closestPair = (p, q) return closestPair
حالت صفحه[ویرایش]
مسئله با استفاده از الگوریتم تقسیم و حل در زمانO(n log n) قابل حل است. رویه در زیر قابل مشاهده است.
- نقاط را براساس مولفهٔ xشان مرتب میکنیم.
- مجموعهٔ نقاط را با استفاده از یک خط عمودی به صورت x=xmid به دو زیرمجموعهٔ با اندازهٔ مساوی تقسیم میکنیم.
- مسئله را به صورت بازگشتی برای زیرمجموعههای راست و چپ حل میکنیم که کمینهٔ فاصله برای سمت راست و چپ به ترتیب به صورت dRmin و dLmin به دست میآید.
- کمینه فاصله بین نقاطی را که یکیشان درزیرمجموعهٔ سمت چپ قرار دارد و دیگری در زیرمجموعهٔ سمت راست انتخاب میکنیم و آن را d»LRmin مینامیم.
- جواب نهایی کمینه فاصله میان dLRmin dLmin dRmin است.
به نظر میرسد مرحلهٔ ۴ در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبهٔ فاصلهٔ همهٔ زوج نقاط در چپ و راست است که نیازمند زمان از مرتبهٔ O(n2) است. نکتهٔ اصلی در خاصیت پراکندگی مجموعهٔ نقاط است. میدانیم که نزدیکترین زوج نقاط قطعاً فاصلهای بیشتر از dist= min(dLmin, dRmin) ندارد. پس کافیست برای هر نقطه در سمت چپ خط جدا کننده، کافی است نقاطی را که در مستطیلی به ابعاد(dist, 2 ⋅ dist) در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش دادهشده است. به علاوه این مستطیل حداکثر ۶ نقطه میتواند در خود جای دهد که حداکثر فاصلهشان dRmin است؛ بنابراین تعداد بهینهٔ محاسبات در مرحلهٔ ۴، حداکثر محاسبهی6n بین زوج نقاطی که یکیشان در سمت چپ و دیگری در سمت راست خط جدا کننده است. رابطهٔ بازگشتی برقرار بین مراحل بالا T(n)T(n) = 2 T(n/2) + O(n) است که با استفاده از قضیه اصلی واکاوی الگوریتمها داریم:T(n) =O(n log n).
همانند مسئله نزدیکترین زوج نقاط، یالی را در مثلثبندی دیلانی تعریف میکنیم که برابر دو خانهٔ مجاور در دیاگرام ورونوی است. نزدیکترین زوج نقاط را با استفاده از دوساختار بالا میتوان در زمان خطی محاسبه کرد. هزینه ایجاد دو ساختارمثلثبندی دیلانی یا دیاگرام ورونوی از لحاظ محاسباتیO(n log n) است. در حالی که رهیافت تقسیم و حل برای تمام ابعاد هزینهٔ محاسباتی ثابتی برابر O(n log n) دارد، این روشها برای بعدهای بیش از ۲ این روشها مناسب نیستند.
یادداشتها[ویرایش]
- ↑ ۱٫۰ ۱٫۱ M. I. Shamos and D. Hoey. "Closest-point problems." In Proc. 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 151—162, 1975 (DOI 10.1109/SFCS.1975.8)
- ↑ S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979
- ↑ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput. , 118(1):34—37,1995
- ↑ Richard Lipton (24 September 2011). "Rabin Flips a Coin".
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- Thomas H. Cormen, Charles E. Leiserson, رونالد ریوست، and کلیفورد استین. مقدمهای بر الگوریتمها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.
- Jon Kleinberg; Éva Tardos (2006). Algorithm Design. Addison Wesley.
- UCSB Lecture Notes
- rosettacode.org - Closest pair of points implemented in multiple programming languages
- Line sweep algorithm for the closest pair problem