ปัญหาคู่จุดที่ใกล้ที่สุด (Closest Pair of Points)

ในปัญหานี้ กำหนดชุดของ n จุดบนระนาบ 2 มิติ เราต้องหาคู่ของจุดที่มีระยะห่างระหว่างกันน้อยที่สุด

วิธีแก้คือการแบ่งจุดออกเป็นสองครึ่ง คำนวณระยะห่างที่น้อยที่สุดในแต่ละครึ่งแบบเรียกซ้ำ (Recursive) จากนั้นพิจารณาจุดที่อยู่ใกล้เส้นแบ่งกลาง (Strip) เพื่อหาคู่ที่อาจมีระยะห่างน้อยกว่าที่พบในแต่ละครึ่ง

อัลกอริทึมนี้มีความซับซ้อนของเวลา O(n log n)

การรับค่าและแสดงผล

Input: ชุดจุดต่างๆ
(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)

Output: ระยะห่างขั้นต่ำจากทุกคู่ของจุด
ผลลัพธ์: 1.41421 หน่วย

อัลกอริทึม

findMinDist(pointsList, n) - หาระยะห่างขั้นต่ำแบบ brute force สำหรับ n ≤ 3

stripClose(strips, size, dist) - หาระยะห่างขั้นต่ำในพื้นที่ strip

findClosest(xSorted, ySorted, n) - ฟังก์ชันหลักแบ่งและเอาชนะ

Begin
  if n <= 3 then
    return findMinDist(xSorted, n)
  
  mid := n/2
  midpoint := xSorted[mid]
  
  แบ่ง ySorted เป็น ySortedLeft และ ySortedRight ตามเส้นแบ่งกลาง
  
  leftDist := findClosest(xSorted, ySortedLeft, mid)
  rightDist := findClosest(xSorted, ySortedRight, n - mid)
  dist := min(leftDist, rightDist)
  
  สร้าง strip จากจุดที่อยู่ห่างจากเส้นกลางน้อยกว่า dist
  close := stripClose(strip, j, dist)
  
  return min(close, dist)
End

ตัวอย่างโค้ด (C++)

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

struct point { int x, y; };

int cmpX(point p1, point p2) { return (p1.x < p2.x); }
int cmpY(point p1, point p2) { return (p1.y < p2.y); }

float dist(point p1, point 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) {
  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 stripClose(point strip[], int size, float d) {
  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], ySortedRight[n-mid-1];
  int leftIndex = 0, rightIndex = 0;
  
  for (int i = 0; i < n; i++) {
    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];
  int j = 0;
  for (int i = 0; i < n; i++)
    if (abs(ySorted[i].x - midPoint.x) < dist)
      strip[j++] = ySorted[i];
  
  return min(dist, stripClose(strip, j, dist));
}

float closestPair(point pts[], int n) {
  point xSorted[n], 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