अंकों की निकटतम जोड़ी समस्या

इस समस्या में, 2D समतल पर n बिंदुओं का एक सेट दिया जाता है। इस समस्या में हमें उन बिंदुओं का युग्म खोजना होता है, जिनकी दूरी न्यूनतम हो।

इस समस्या को हल करने के लिए, हमें बिंदुओं को दो हिस्सों में विभाजित करना होगा, उसके बाद दो बिंदुओं के बीच की सबसे छोटी दूरी की गणना पुनरावर्ती तरीके से की जाती है। मध्य रेखा से दूरियों का उपयोग करते हुए, बिंदुओं को कुछ पट्टियों में विभाजित किया जाता है। हम स्ट्रिप ऐरे से सबसे छोटी दूरी पाएंगे। पहले दो सूचियाँ डेटा बिंदुओं के साथ बनाई जाती हैं, एक सूची में ऐसे बिंदु होंगे जो x मानों पर सॉर्ट किए गए हैं, दूसरी सूची y मानों पर सॉर्ट किए गए डेटा बिंदुओं को रखेगी।

इस एल्गोरिथम की समय जटिलता O(n log n) होगी।

इनपुट और आउटपुट

Input:
A set of different points are given. (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)
Output:
Find the minimum distance from each pair of given points.
Here the minimum distance is: 1.41421 unit

एल्गोरिदम

findMinDist(pointsList, n)

इनपुट: दी गई बिंदु सूची और सूची में अंकों की संख्या।

आउटपुट - दो बिंदुओं से न्यूनतम दूरी पाता है।

Begin
   min := ∞
   for all items i in the pointsList, do
      for j := i+1 to n-1, do
         if distance between pointList[i] and pointList[j] < min, then
            min = distance of pointList[i] and pointList[j]
     done
   done
   return min
End

stripClose(strips, size, dist)

इनपुट - पट्टी में विभिन्न बिंदु, अंकों की संख्या, मध्य रेखा से दूरी।

आउटपुट - एक पट्टी में दो बिंदुओं से निकटतम दूरी।

Begin
   for all items i in the strip, do
      for j := i+1 to size-1 and (y difference of ithand jth points) <min, do
         if distance between strip[i] and strip [j] < min, then
            min = distance of strip [i] and strip [j]
      done
   done
   return min
End

ढूंढें निकटतम(xSorted, ySorted, n)

इनपुट - अंक x मानों के आधार पर क्रमबद्ध किए गए, और अंक y मानों के आधार पर क्रमबद्ध किए गए, अंकों की संख्या।

आउटपुट - अंकों के कुल सेट से न्यूनतम दूरी ज्ञात करें।

Begin
   if n <= 3, then
      call findMinDist(xSorted, n)
      return the result
   mid := n/2
   midpoint := xSorted[mid]
   define two sub lists of points to separate points along vertical line.
   the sub lists are, ySortedLeft and ySortedRight

   leftDist := findClosest(xSorted, ySortedLeft, mid)         //find left distance
   rightDist := findClosest(xSorted, ySortedRight, n - mid)   //find right distance

   dist := minimum of leftDist and rightDist

   make strip of points
   j := 0
   for i := 0 to n-1, do
      if difference of ySorted[i].x and midPoint.x<dist, then
         strip[j] := ySorted[i]
         j := j+1
   done

   close := stripClose(strip, j, dist)
   return minimum of close and dist
End

उदाहरण

#include <iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct point {
   int x, y;
};

intcmpX(point p1, point p2) {    //to sort according to x value
   return (p1.x < p2.x);
}

intcmpY(point p1, point p2) {    //to sort according to y value
   return (p1.y < p2.y);
}

float dist(point p1, point p2) {    //find distance between p1 and p2
   return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

float findMinDist(point pts[], int n) {    //find minimum distance between two points in a set
   float min = 9999;
   for (int i = 0; i < n; ++i)
      for (int j = i+1; j < n; ++j)
         if (dist(pts[i], pts[j]) < min)
            min = dist(pts[i], pts[j]);
   return min;
}

float min(float a, float b) {
   return (a < b)? a : b;
}

float stripClose(point strip[], int size, float d) {    //find closest distance of two points in a strip
   float min = d;
   for (int i = 0; i < size; ++i)
      for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
         if (dist(strip[i],strip[j]) < min)
            min = dist(strip[i], strip[j]);
   return min;
}

float findClosest(point xSorted[], point ySorted[], int n){
   if (n <= 3)
      return findMinDist(xSorted, n);
   int mid = n/2;

   point midPoint = xSorted[mid];
   point ySortedLeft[mid+1];     // y sorted points in the left side
   point ySortedRight[n-mid-1];  // y sorted points in the right side
   intleftIndex = 0, rightIndex = 0;

   for (int i = 0; i < n; i++) {       //separate y sorted points to left and right
      if (ySorted[i].x <= midPoint.x)
         ySortedLeft[leftIndex++] = ySorted[i];
      else
         ySortedRight[rightIndex++] = ySorted[i];
   }

   float leftDist = findClosest(xSorted, ySortedLeft, mid);
   float rightDist = findClosest(ySorted + mid, ySortedRight, n-mid);
   float dist = min(leftDist, rightDist);

   point strip[n];      //hold points closer to the vertical line
   int j = 0;

   for (int i = 0; i < n; i++)
      if (abs(ySorted[i].x - midPoint.x) <dist) {
         strip[j] = ySorted[i];
         j++;
      }
   return min(dist, stripClose(strip, j, dist));    //find minimum using dist and closest pair in strip
}

float closestPair(point pts[], int n) {    //find distance of closest pair in a set of points
   point xSorted[n];
   point ySorted[n];

   for (int i = 0; i < n; i++) {
      xSorted[i] = pts[i];
      ySorted[i] = pts[i];
   }

   sort(xSorted, xSorted+n, cmpX);
   sort(ySorted, ySorted+n, cmpY);
   return findClosest(xSorted, ySorted, n);
}

int main() {
   point P[] ={{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
   int n = 6;
   cout<< "The minimum distance is " <<closestPair(P, n);
}

आउटपुट

The minimum distance is 1.41421