نمایش مبدأ برای تعیین نزدیکترین زوج نقاط در فضای دو بعدی

{{ویکی‌سازی}}

[[پرونده:Closest pair of points.svg|راست|بندانگشتی|نزدیک‌ترین زوج نقطه با رنگ قرمز نشان داده شده است.]]

'''مسئله نزدیکترین زوج نقاط''' یا '''نزدیکترین زوج''' یک مسئله از [[هندسه محاسباتی]] است که در آن در [[فضای متری]] n نقطه به عنوان ورودی گرفته می‌شود و زوج نقطه‌ای که کوتاه‌ترین فاصله بین آن‌دو وجود دارد، پیدا می‌شود. مسئله نزدیکترین زوج برای نقاط در صفحهٔ اقلیدسی<ref name=sh>[[Michael Ian Shamos|M. I. Shamos]] and [[Dan Hoey|D. Hoey]]. [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4567872 "Closest-point problems."] In ''Proc. 16th Annual [[IEEE]] [[Symposium on Foundations of Computer Science]]'' (FOCS), pp. 151&mdash;162, 1975 (DOI [http://dx.doi.org/10.1109/SFCS.1975.8 10.1109/SFCS.1975.8])</ref> از اولین مسائل هندسه بود که مطالعات سیستماتیک در [[نظریه پیچیدگی محاسباتی]]، الگوریتم‌های هندسه شد.

الگوریتم ساده، پیدا کردن فاصلهٔ همهٔ زوج نقاط و انتخاب کمینهٔ آن‌هاست که نیازمند زمانی از مرتبهٔ <math> O(n^2)</math>است. به نظر می‌رسد مسئله در زمان <math>O(nlgn)</math>در [[فضای اقلیدسی]] با بعد ثابت <math>d </math>قابل حل باشد. در [[درخت تصمیم]] جبری [[مدل محاسبه]] الگوریتم با زمان <math>O(nlgn
)</math>با توجه به کاهشی از [[مساله یکتایی عنصر]] بهینه است. در مدل محاسباتی چنین فرض می‌شود که [[تابع کف]] در زمان ثابت قابل محاسبه است و مساله می‌تواند در <math>O(nlglgn)</math>حل شود.<ref name="fh">S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20&mdash;23, 1979</ref> اگر در تابع کف از حالت تصادفی استفاده کنیم مسئله در <math>O(n)</math>نیز قابل حل است.<ref name="km">S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput. , 118(1):34&mdash;37,1995</ref><ref name="rl">{{cite web |url=http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ |title=Rabin Flips a Coin |author= Richard Lipton|date=24 September 2011}}</ref>

== جستجوی جامع ==
نزدیکترین زوج از نقاط با استتفاده از [[جستجوی جامع]] در [[زمان|نظریه پیچیدگی محاسباتی]] <math>O(n^2)</math>قابل محاسبه است. برای این کار باید فاصلهٔ میان تمام<math>\frac{n(n-1)}{2}</math> زوج نقطه را محاسبه کرده و زوجی را که کم‌ترین فاصله را دارند، انتحاب کنیم. [[شبه‌کد|شبه کد]] این الگوریتم در زیرمشاهده می‌شود.<ref name=sh /><syntaxhighlight line="1">
minDist = infinity
for i = 1 to length(P) - 1
 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
</syntaxhighlight>

== حالت صفحه ==
مسئله با استفاده از [[الگوریتم تقسیم و حل]] در زمان <math>O(nlogn
)</math>قابل حل است. رویه در زیر قابل مشاهده است.
# نقاط را براساس مولفهٔ <math>x</math>آن‌ها مرتب می‌کنیم.
# مجموعهٔ نقاط را با استفاده از یک خط عمودی به صورت <math>x = x_{mid}</math>به دو زیرمجموعهٔ با اندازهٔ مساوی تقسیم می‌کنیم.
# مسئله را به صورت بازگشتی برای زیرمجموعه‌های راست و چپ حل می‌کنیم که کمینهٔ فاصله برای سمت راست و چپ به ترتیب به صورت <math>d_{Rmin}</math>و <math>d_{Lmin}</math>به دست می‌آید.
# کمینه فاصله بین نقاطی را که یکی‌شان در زیرمجموعهٔ سمت چپ قرار دارد و دیگری در زیرمجموعهٔ سمت راست انتخاب می‌کنیم و آن را <math>d_{LRmin}</math> می‌نامیم.
# جواب نهایی کمینه فاصله میان <math>d_{LRmin}</math> <math>d_{Lmin}</math> <math>d_{Rmin}</math> است.

به نظر می‌رسد مرحلهٔ ۴ در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبهٔ فاصلهٔ همهٔ زوج نقاط در چپ و راست است که نیازمند زمان از مرتبهٔ <math>O(n^2)</math> است. نکتهٔ اصلی در خاصیت پراکندگی مجموعهٔ نقاط است. می‌دانیم که نزدیک‌ترین زوج نقاط قطعاً فاصله‌ای بیش‌تر از <math>dist = \min(d_{Lmin}, d_{Rmin})</math> ندارد. پس کافی‌ست برای هر نقطه در سمت چپ خط جدا کننده، کافی است نقاطی را که در مستطیلی به ابعاد<math>(dist, 2*dist)</math> در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش داده‌شده است. به علاوه این مستطیل حداکثر ۶ نقطه می‌تواند در خود جای دهد که حداکثر فاصله‌شان <math>d_{Rmin}</math> است؛ بنابراین تعداد بهینهٔ محاسبات در مرحلهٔ ۴، حداکثر محاسبه‌ی <math>6n</math>بین زوج نقاطی که یکی‌شان در سمت چپ و دیگری در سمت راست خط جدا کننده است. [[رابطه بازگشتی|رابطهٔ بازگشتی]] برقرار بین مراحل بالا <math>T(n) = 2T(\frac{n}{2}) + O(n)</math> است که با استفاده از [[قضیه اصلی واکاوی الگوریتم‌ها]] داریم:<math>O(nlgn)</math>.

[[پرونده:Closest pair.jpg|راست|بندانگشتی|تقسیم وحل: مستطیل جدا کننده]]

همانند مسئله نزدیکترین زوج نقاط، یالی را در [[مثلث‌بندی دیلانی]] تعریف می‌کنیم که برابر دو خانهٔ مجاور در [[دیاگرام ورونوی]] است. نزدیک‌ترین زوج نقاط را با استفاده از دوساختار بالا می‌توان در زمان خطی محاسبه کرد. هزینه ایجاد دو ساختارمثلث‌بندی دیلانی یا دیاگرام ورونوی از لحاظ محاسباتی<math>O(nlgn)</math> است. در حالی که ره‌یافت تقسیم و حل برای تمام ابعاد هزینهٔ محاسباتی ثابتی برابر <math>O(nlgn)</math> دارد، این روش‌ها برای بعدهای بیش از ۲ این روش‌ها مناسب نیستند.

<syntaxhighlight lang="text">
Algorithm Closest_Pair(p1, p2, ..., pn);
Input: p1, p2, ..., pn (a set of n points in the plane)
Output: d (the distance between the two closest points in the set)

begin
    sort the points according to their x coordinates;
    {''this sorting is done only once at the beginning''}
    Didive the set into two equal-sized parts;
    Recursively do the following:
        compute the minimal distance in each part;
        sort the points in each part according to their y coordinates;
    Merge the two sorted lists into one sorted list;
    {''Notice that we must merge before we eliminate; 
        we need to supply the whole set sorted to the next level of the recursion''}
    Let d be the minimal of the minimal distances;
    Eliminate points that lie further than d apart from the seperation line;
    Scan the points in the y order and compute the distances of each point to its five neighbors;
    if any of these distances is less than d the update d;
end
</syntaxhighlight><ref>{{یادکرد کتاب|عنوان=آشنایی با الگوریتم‌ها با رویکرد خلاقانه|نام خانوادگی=منبر|نام=یودی|ناشر=دانش پژوهان جوان|سال=1396|شابک=978-600-288-079-6|مکان=تهران|صفحات=400}}</ref>

== یادداشت‌ها ==
{{پانویس}}

== جستارهای وابسته ==
* [[جستجوی نزدیکترین همسایه]]
* [[پوشش مجموعه]]

== منابع ==
{{refbegin}}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[رونالد ریوست]]، and [[کلیفورد استین]]. ''[[مقدمه‌ای بر الگوریتم‌ها]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7|en}}. Pages 957–961 of section 33.4: Finding the closest pair of points.
* {{cite book
  | author = Jon Kleinberg; Éva Tardos
  | title = Algorithm Design
  | publisher = Addison Wesley
  | year = 2006}}
*[http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf UCSB Lecture Notes]
*[http://rosettacode.org/wiki/Closest-pair_problem rosettacode.org] - Closest pair of points implemented in multiple programming languages
*[http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep Line sweep algorithm for the closest pair problem]
{{refend}}

[[رده:الگوریتم‌های هندسی]]