BÀI TOÁN CẶP ĐIỂM GẦN NHẤT
I. Mở đầu
§a sè c¸c thuËt to¸n ®Òu tËp trung xö lÝ trªn v¨n b¶n (xö lÝ trªn x©u) vµ
c¸c con sè, chóng ®-îc thiÕt kÕ vµ xö lÝ s½n trong phÇn lín c¸c bµi to¸n lËp
tr×nh. §èi víi c¸c bµi to¸n h×nh häc th× ®ßi hái kh¸c h¼n, ng-êi lËp tr×nh ph¶i cã
sù tÝnh to¸n tØ mØ c¸c c«ng thøc vÒ h×nh häc tr-íc khi ®i vµo lËp tr×nh. Khi lµm
c¸c bµi tËp vÒ h×nh häc th-êng ph¶i ®ßi hái sù c«ng phu lËp tr×nh h¬n c¸c bµi
tËp kh¸c, nhÊt lµ viÖc thiÕt lËp c¸c c«ng thøc th× bµi lËp tr×nh míi cã hiÖu qu¶.
1. §èi t-îng h×nh häc c¬ b¶n
Trong c¸c bµi to¸n Tin häc thuéc lo¹i h×nh häc cã 3 ®èi t-îng c¬ b¶n lµ: §iÓm,
§o¹n th¼ng vµ §a gi¸c.
§iÓm: §-îc xÐt b»ng mét cÆp sè nguyªn lµ täa ®é cña ®iÓm ®ã trong hÖ trôc
täa ®é Descartes th-êng dïng.
§o¹n th¼ng: Lµ mét cÆp ®iÓm ®-îc nèi víi nhau mét phÇn cña ®-êng th¼ng.
§a gi¸c: Lµ mét d·y c¸c ®iÓm víi hai ®iÓm liªn tiÕp ®-îc nèi bëi mét ®o¹n
th¼ng, vµ ®iÓm ®Çu ®-îc nèi víi ®iÓm cuèi t¹o thµnh mét h×nh gÊp khóc khÐp
kÝn.
2. D÷ liÖu l-u tr÷ c¸c ®èi t-îng h×nh häc c¬ b¶n
Lµm viÖc víi c¸c ®èi t-îng h×nh häc chóng ta cÇn quyÕt ®Þnh thÓ hiÖn
chóng nh- thÕ nµo? Th«ng th-êng ta dïng mét m¶ng ®Ó biÓu diÔn mét ®a gi¸c,
dï r»ng mét sè tr-êng hîp kh¸c chóng ta cã thÓ dïng danh s¸ch liªn kÕt hay
c¸c kiÓu kh¸c. §èi t-îng chóng ta th-êng xuyªn ph¶i lµm viÖc víi h×nh häc lµ
täa ®é, do ®ã viÖc l-u tr÷ to¹ ®é cña c¸c ®iÓm lµ phæ biÕn trong c¸c bµi to¸n lËp
tr×nh vÒ h×nh häc.
II. Nội dung
1
1. Phát biểu bài toán
Bài toán: Cho𝑁 điểm trên mặt mẳng tọa độ, tìm khoảng cách ngắn nhất
giữa hai điểm bất kỳ.
2. Thuật toán
Bài toán này ta có thể dễ dàng thực hiện thuật toán 𝑏𝑟𝑢𝑡𝑒𝑓𝑜𝑟𝑐𝑒, ta xét tất cả
các cặp điểm và chọn cặp có khoảng cách ngắn nhất giữa chúng. Thuật toán có
độ phức tạp 𝑂(𝑛2 ). Ta có một số thuật toán tốt hơn như sau:
2.1.Thuật toán chia để trị
a. Ý tưởng thuật toán
Thuật toán chia để trị giải quyết bài toán này thực hiện như sau:
Sắp xếp các điểm đã cho theo thứ tự từ trái sang phải. Chia tập điểm
thành hai tập.
Thực hiện thao tác đệ quy, tìm cặp điểm gần nhất trong hai tập con, trả
lại giá trị là khoảng cách ngắn nhất trong tập đó.
Gọi 𝛿 là khoảng cách ngắn nhất, trong hai khoảng cách ngắn nhất trong
hai tập con. Ta chỉ quan tâm tới các cặp có khoảng cách nhỏ hơn 𝛿.
Xét trong “cửa sổ” độ rộng 2𝛿, sắp xếp tất cả các điểm trong cửa sổ đó
2
theo thứ tự tăng dần chiều tọa độ 𝑦.
Nhận xét: vì khoảng cách giữa mỗi cặp điểm bất kỳ trên hai tập không
nhỏ hơn 𝛿 nên với mỗi một điểm trên “cửa sổ”, có không quá 3 điểm
mỗi bên có khoảng cách 𝑡ọ𝑎 độ 𝑦 nhỏ hơn hoặc bằng 𝛿 so với điểm đó.
Do vậy, với mỗi điểm, ta chỉ cần xét (ghép cặp) không quá 6 điểm để có
thể tìm ra cặp điểm có khoảng cách Euclid nhỏ hơn 𝛿.
b. Cài đặt
Sử dụng đệ quy quay lui để cài đặt thuật toán. Với mỗi đoạn:
Nếu độ dài đoạn 𝑛 ≤ 3, ta tính toán bruteforce để tìm cặp điểm gần
nhất.
Nếu độ dài 𝑛 ≥ 3 ta chia đôi tập, đệ quy quay lui để tính khoảng cách
gần nhất trong hai tập con, chọn giá trị bé nhất trong hai khoảng cách.
Dùng mảng 𝑠𝑡𝑟𝑖𝑝 để trộn hai phía theo thứ tự tăng dần 𝑦, lọc lấy những
phần tử có chênh lệch 𝑦 nhỏ hơn giá trị 𝑚𝑖𝑛 đang có. (𝑑). Chú ý sau khi
thực hiện, ta thực hiện sắp xếp trộn hai phía của đoạn theo thứ tự tăng
dần y luôn, độ phức tạp 𝑂(𝑛), không sử dụng thuật toán sắp xếp khác.
Với các phần tử trong cửa sổ, với mỗi điểm, xét các điểm lân cận (sau
khi đã sắp xếp) có chênh lệch 𝑦 nhỏ hơn 𝑑. (số phần tử này ≤ 6)
3
Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán chia
để trị:
Input:
Dòng đầu tiên là số𝑁 – số lượng điểm(𝑛 ≤ 2.105 )
𝑁dòng tiếp theo, mỗi dòng chứa tọa độ một điểm theo thứ tự.
Output: Khoảng cách nhỏ nhất cần tìm, chính xác 5 chữ số phần thập phân.
CLOSESTPAIR.INP
3
1 1
2 2
2 1
CLOSESTPAIR.OUT
1.00000
Chương trình:
#include
#define sz(x) int(x.size())
#define MIN(x,y) if (x < y) x = y
#define PB push_back
#define mp make_pair
#define Task "closestpair"
#define maxn 200002
#define MOD 1000000007
#define remain(x) if (x > MOD) x -= MOD
#define pii pair
#define X first
#define Y second
using namespace std;
pii a[maxn], strip[maxn];
double ans = 1e10;
double Distance(pii P1, pii P2)
{
double XX = P1.X - P2.X;
4
double YY = P1.Y - P2.Y;
return sqrt(XX*XX + YY*YY);
}
double bruteForce(pii P[], int n)
{
double kmin = FLT_MAX;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
kmin = min(kmin, Distance(P[i], P[j]));
return kmin;
}
bool compareY(pii p1, pii p2)
{
return (p1.Y < p2.Y || (p1.Y == p2.Y && p1.X < p2.X));
}
double stripClosest(pii strip[], int n, double d)
{
double kmin = d;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n && (strip[j].Y - strip[i].Y) <
kmin; j++)
kmin = min(Distance(strip[i],strip[j]), kmin);
return kmin;
}
double Calc(pii P[], int n)
{
if (n <= 3)
{
sort (P, P+n, compareY);
return bruteForce(P, n);
}
int mid = n/2;
pii midPoint = P[mid];
double dl = Calc(P, mid);
double dr = Calc(P + mid, n-mid);
double d = min(dl, dr);
5
int ccount = 0;
merge(P, P+mid, P+mid, P+n, strip,compareY);
for (int i = 0; i < n; i++)
{
P[i] = strip[i];
if (abs(strip[i].X - midPoint.X) < d)
strip[ccount++] = strip[i];
}
return min(d, stripClosest(strip, ccount, d));
}
double Closest(pii a[], int n)
{
sort(a, a+n);
return Calc(a,n);
}
int main()
{
ios_base::sync_with_stdio(0);
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y;
printf("%0.5f", Closest(a,n));
return 0;
}
c. Đánh giá
Việc tính trong cửa sổ 2𝛿 và sắp xếp trộn với một đoạn độ dài 𝑛 (không
tính hai đoạn con) có độ phức tạp O(n). Số lần lặp thủ tục tính có lời gọi
không quá log 2 𝑛 lần nên tổng độ phức tạp thuật toán là 𝑂(𝑛𝑙𝑔𝑛).
6
2.2.Thuật toán sweep line
a. Ý tưởng thuật toán.
Sắp xếp tọa độ các điểm theo chiều 𝑥.
Xét từng điểm từ trái qua phải. Giả sử ta đang xét tới điểm 𝑝 và giá trị
nhỏ nhất giữa hai điểm trong các điểm bên trái 𝑝là 𝑑. Rõ ràng ta chỉ giữ
lại những điểm có khoảng cách tới tọa độ 𝑥 của 𝑝 là 𝛿 < 𝑑 (hình trái)
Với điểm 𝑝 ta chỉ cần xét những điểm có chênh lệch cả 𝑥 và 𝑦 so với 𝑝
không quá 𝑑. (hình bên phải). Dễ thấy, vì 𝑑 là khoảng cách ngắn nhất
giữa 2 điểm trong tập điểm bên trái đã xét nên chắc chắn có không quá 4
điểm như vậy.
b. Cài đặt
Sử dụng thêm cấu trúc set để lưu trữ các phần tử trong “vệt quét” hay nói
cách khác là các phần tử có tọa độ x có khoảng cách tới tọa độ x của p
đang xét nhỏ hơn giá trị d hiện tại. Đồng thời dễ ràng thêm, xóa và tìm
kiếm các phần tử trong phạm vi 𝑝. 𝑦 − 𝑑 → 𝑝. 𝑦 + 𝑑.
7
Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán
sweepline:
#include
#define sz(x) int(x.size())
#define MIN(x,y) if (x < y) x = y
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define Task "closestpair"
#define maxn 200002
#define MOD 1000000007
#define remain(x) if (x > MOD) x -= MOD
#define pii pair
#define Y first
#define X second
using namespace std;
pii a[maxn];
set S;
double Distance(pii P1, pii P2)
{
double XX = P1.X - P2.X;
double YY = P1.Y - P2.Y;
return sqrt(XX*XX + YY*YY);
}
bool compareX(pii p1, pii p2)
{
return (p1.X < p2.X || (p1.X == p2.X && p1.Y < p2.Y));
}
double Closest(pii a[], int n)
{
sort(a, a+n, compareX);
S.insert(a[0]);
int left = 0;
8
double ans = 1e10;
for (int i = 1; i < n; i++)
{
int py = a[i].Y;
int px = a[i].X;
while (a[left].X < px - ans) S.erase(a[left++]);
for
(set
::
iterator
it
=
S.lower_bound(mp(1.0*py-ans, 1.0*px-ans)); it != S.end()
&& it->Y < ans+py; it++)
ans = min (ans, Distance(*it, a[i]));
S.insert(a[i]);
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y;
printf("%0.5f", Closest(a,n));
return 0;
}
c. Đánh giá
Mỗi điểm được thêm vào và xóa đi trong Set đúng 1 lần (𝑙𝑔𝑛) nên thời
gian xử lí thêm vào và xóa đi trên Set là 𝑂(𝑛 𝑙𝑔𝑛). Với mỗi điểm 𝑝 việc
tìm vị trí bắt đầu có tọa độ trong phạm vi 𝑝. 𝑦 − 𝑑 (hàm lower-bound)
mất chi phí thời gian 𝑙𝑔𝑛. Số điểm để thuộc hình chữ nhật có thể xét
luôn không vượt quá 4. Do vậy, tổng độ phức tạp để thực hiện giải thuật
là 𝑂(𝑛𝑙𝑔𝑛).
9
III.Kết luận
Với bài toán cặp điểm gần nhất, cả hai thuật toán chia để trị và
sweepline đã trình bày trên đều có độ phức tạp là 𝑂(𝑛𝑙𝑔𝑛). Việc cài
đặt thuật toán sweepline được cài đặt đơn giản, ngắn gọn hơn (khi sử
dụng ngôn ngữ C++). Tuy nhiên, về mặt thời gian, thuật toán chia để
trị lại thực hiện hiệu quả hơn do việc xử lý Set trong C++ tốn nhiều
thời gian hơn.
Tài liệu tham khảo
1. Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein, Introduction To Algorithms, Third Edition.
2. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars,
Computational Geometry Algorithms and Appliacitons, Third Edition.
10