アルゴリズムの概要は以下の通りです。
-
入力として、二次元平面上の点の集合が与えられるとします。
-
まず、入力点集合をx座標に基づいてソートします。これにより、後の処理で点の組み合わせを効率的に処理することができます。
-
分割統治法を使用して、最も近い点のペアを見つけます。
a. 入力点集合をx軸について中央で分割し、左右の部分集合に分けます。
b. 左右の部分集合それぞれに対して再帰的に最も近い点のペアを見つけます。
c. 左右の部分集合における最も近い点のペアを比較し、より近い方を採用します。
-
分割統治法の処理が終わったら、最も近い点のペアが見つかります。
以下に、C++での実装例を示します。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
struct Point {
int x, y;
};
// 2点間の距離を計算する関数
double distance(Point p1, Point p2) {
int dx = p1.x - p2.x;
int dy = p1.y - p2.y;
return sqrt(dx*dx + dy*dy);
}
// x座標に基づいて点をソートする関数
bool compareX(Point p1, Point p2) {
return p1.x < p2.x;
}
// 最も近い点のペアを見つける再帰関数
pair<Point, Point> closestPairUtil(vector<Point>& points, int left, int right) {
if (right - left <= 3) {
// 小さい部分問題に対して総当たりで最も近い点のペアを見つける
double minDist = INT_MAX;
pair<Point, Point> closestPair;
for (int i = left; i <= right; i++) {
for (int j = i + 1; j <= right; j++) {
double dist = distance(points[i], points[j]);
if (dist < minDist) {
minDist = dist;
closestPair = make_pair(points[i], points[j]);
}
}
}
return closestPair;
}
// 左右に分割して再帰的に最も近い点のペアを求める
int mid = (left + right) / 2;
pair<Point, Point> closestPairLeft = closestPairUtil(points, left, mid);
pair<Point, Point> closestPairRight = closestPairUtil(points, mid + 1, right);
// 左右の部分問題の結果を比較して最も近い点のペアを選ぶ
double distLeft = distance(closestPairLeft.first, closestPairLeft.second);
double distRight = distance(closestPairRight.first, closestPairRight.second);
double minDist = min(distLeft, distRight);
pair<Point, Point> closestPair = (distLeft < distRight) ? closestPairLeft : closestPairRight;
// 中央の帯状領域における最も近い点のペアを探す
vector<Point> strip;
for (int i = left; i <= right; i++) {
if (abs(points[i].x - points[mid].x) < minDist) {
strip.push_back(points[i]);
}
}
sort(strip.begin(), strip.end(), [](Point p1, Point p2) {
return p1.y < p2.y;
});
int size = strip.size();
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
double dist = distance(strip[i], strip[j]);
if (dist < minDist) {
minDist = dist;
closestPair = make_pair(strip[i], strip[j]);
}
}
}
return closestPair;
}
// 最も近い点のペアを見つける関数
pair<Point, Point> closestPair(vector<Point>& points) {
int n = points.size();
sort(points.begin(), points.end(), compareX);
return closestPairUtil(points, 0, n - 1);
}
int main() {
vector<Point> points = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
pair<Point, Point> closest = closestPair(points);
cout << "Closest pair: (" << closest.first.x << ", " << closest.first.y << "), (" << closest.second.x << ", " << closest.second.y << ")" << endl;
return 0;
}このコードは、与えられた点の集合から最も近い点のペアを見つけるためのO(nlogn)のアルゴリズムを実装しています。与えられた点集合に対してこのアルゴリズムを適用すると、最も近い点のペアが返されます。上記のコードを使用して、与えられた点集合から最も近い点のペアを見つけることができます。
この記事では、最も近い点のペアを見つける問題について解説し、O(nlogn)のアルゴリズムを実装する方法を説明しました。これにより、大規模な点集合でも効率的に最も近い点のペアを見つけることができます。