Tam giác phân Delaunay và sơ đồ Voronoi
Tam giác phân Delaunay, sơ đồ Voronoi và tính đối ngẫu giữa chúng: tính chất đường tròn rỗng, phép thử in-circle chính xác bằng __int128, lật cạnh, thuật toán chia để trị Guibas-Stolfi O(n log n) và ứng dụng dựng cây khung nhỏ nhất Euclid.
Cho điểm trên mặt phẳng. Sơ đồ Voronoi (Voronoi diagram) chia mặt phẳng thành vùng, vùng của điểm gồm mọi vị trí gần hơn mọi điểm khác. Tam giác phân Delaunay (Delaunay triangulation) là đồ thị đối ngẫu của nó: nối hai điểm khi vùng Voronoi của chúng có chung một cạnh. Đồ thị này phẳng, chỉ có không quá cạnh, dựng được trong , và chứa sẵn những cấu trúc "gần" quan trọng: cây khung nhỏ nhất Euclid (EMST), đồ thị láng giềng gần nhất, cặp điểm gần nhất. Nhờ đó bài cây khung nhỏ nhất trên đồ thị đầy đủ điểm (có cạnh) giảm từ xuống : chạy Kruskal trên cạnh Delaunay thay vì trên mọi cặp.
Ý tưởng / Trực giác
Tính chất đường tròn rỗng. Một tam giác phân (chia bao lồi của tập điểm thành các tam giác có đỉnh là các điểm đã cho) là Delaunay khi và chỉ khi đường tròn ngoại tiếp của mỗi tam giác không chứa điểm nào ở bên trong (điểm nằm đúng trên đường tròn thì được phép). Tương đương cho từng cạnh: đoạn là một cạnh Delaunay khi và chỉ khi tồn tại một đường tròn đi qua và mà bên trong không có điểm nào.
Vì sao đối ngẫu với Voronoi. Tâm của đường tròn rỗng đi qua cách đều ba điểm này và mọi điểm khác ở xa hơn (vì nằm ngoài đường tròn). Vậy là điểm thuộc cả ba vùng Voronoi của : đó chính là một đỉnh Voronoi. Tương tự, nếu có đường tròn rỗng qua thì tâm của nó nằm trên biên chung của hai vùng Voronoi, nên hai vùng kề nhau. Tóm lại:
| Delaunay | Voronoi |
|---|---|
| điểm | vùng (cell) của |
| cạnh | cạnh Voronoi, nằm trên trung trực của |
| tam giác | đỉnh Voronoi = tâm đường tròn ngoại tiếp |
| cạnh trên bao lồi | cạnh Voronoi vô hạn (tia) |
Vì sao chứa EMST. Lấy một cạnh của cây khung nhỏ nhất Euclid. Xét đường tròn đường kính . Nếu có điểm nằm trong đường tròn đó thì góc , nên và . Bỏ cạnh khỏi cây, cây tách thành hai phần, nằm ở một phần; nối với đầu mút ở phần kia bằng cạnh ngắn hơn cho cây nhẹ hơn, mâu thuẫn. Vậy đường tròn đường kính rỗng, và là cạnh Delaunay. Với trọng số bằng nhau thì có thể có nhiều EMST, nhưng lập luận "luôn có đường đi trong Delaunay với cạnh lớn nhất không vượt quá " vẫn đúng, nên Kruskal trên các cạnh Delaunay cho đúng trọng số EMST. Láng giềng gần nhất của mỗi điểm là trường hợp riêng: nếu gần nhất thì đường tròn đường kính (thậm chí đường tròn tâm bán kính ) không chứa điểm nào khác, nên cặp điểm gần nhất cũng là một cạnh Delaunay.
Phép thử trong đường tròn (in-circle). Với ba điểm xếp ngược chiều kim đồng hồ và điểm , dời gốc tọa độ về (đặt , ...) rồi tính
khi nằm trong đường tròn ngoại tiếp , khi nằm trên, khi nằm ngoài. Đây là định thức quen thuộc với các hàng : nâng mỗi điểm lên paraboloid , khi đó " trong đường tròn qua " tương đương " nâng lên nằm dưới mặt phẳng qua ba điểm nâng lên". Cũng từ hình ảnh này: tam giác phân Delaunay chính là hình chiếu xuống của mặt dưới bao lồi 3 chiều của các điểm đã nâng.
Với tọa độ nguyên, mọi phép so sánh đều làm chính xác bằng số nguyên: tích có ngoài dùng long long, còn định thức là bậc nên phải dùng __int128. Không có eps, không có sai số.
Phép lật cạnh (edge flip). Xét hai tam giác chung cạnh tạo thành tứ giác lồi . Nếu nằm trong đường tròn ngoại tiếp thì cạnh là không hợp lệ; thay nó bằng đường chéo kia thì cả hai tam giác mới đều hợp lệ. Định lý (Lawson): một tam giác phân mà mọi cạnh đều hợp lệ cục bộ thì là Delaunay. Mỗi lần lật làm tăng (theo thứ tự từ điển) dãy các góc đã sắp xếp của tam giác phân, nên quá trình lật luôn dừng. Hệ quả đẹp: trong mọi tam giác phân của tập điểm, Delaunay là tam giác phân có góc nhỏ nhất lớn nhất (tránh các tam giác "mảnh").
Ví dụ chạy tay
Một lần lật cạnh. Bốn điểm , , , . Tam giác phân dùng đường chéo dài :
graph 4 1 2 2 3 3 4 4 1 1 3 name 1 P name 2 Q name 3 R name 4 S pos 1 0 60 pos 2 160 100 pos 3 320 60 pos 4 160 20 highlight red 1-3
Thử với đường tròn ngoại tiếp tam giác (ngược chiều kim đồng hồ). Dời gốc về : , , , nên , , và , , :
nằm trong đường tròn (đường tròn qua có tâm , bán kính , còn chỉ cách tâm ), nên không hợp lệ. Lật sang đường chéo :
graph 4 1 2 2 3 3 4 4 1 2 4 name 1 P name 2 Q name 3 R name 4 S pos 1 0 60 pos 2 160 100 pos 3 320 60 pos 4 160 20 highlight green 2-4
Kiểm tra lại: thử với tam giác cho , ở ngoài; theo đối xứng cũng ở ngoài đường tròn . Hai tam giác mới "béo" hơn hẳn hai tam giác dẹt ban đầu.
Tam giác phân và EMST của điểm. Đánh số các điểm theo thứ tự tăng dần:
| đỉnh | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| tọa độ |
Bao lồi có đỉnh (), nên mọi tam giác phân của tập này có đúng cạnh và tam giác. Tam giác phân Delaunay (chương trình bên dưới in ra đúng cạnh này), các cạnh của EMST tô xanh:
graph 7 1 2 1 3 1 7 2 3 2 4 2 5 3 4 3 6 3 7 4 5 4 6 5 6 6 7 pos 1 0 300 pos 2 50 100 pos 3 150 250 pos 4 150 150 pos 5 150 0 pos 6 250 100 pos 7 300 300 highlight green 3-4 2-4 4-6 2-5 1-3 3-7
Kruskal trên cạnh này, sắp theo bình phương độ dài (so sánh số nguyên, không cần căn):
| cạnh | Kruskal | |
|---|---|---|
| 3-4 | 4 | nhận |
| 2-4 | 5 | nhận |
| 4-6 | 5 | nhận |
| 2-5 | 8 | nhận |
| 5-6 | 8 | bỏ ( và đã nối qua ) |
| 4-5 | 9 | bỏ |
| 1-3 | 10 | nhận |
| 3-7 | 10 | nhận, đủ cạnh |
Tổng độ dài .
Vùng Voronoi của đỉnh 4. Đỉnh có láng giềng Delaunay và nằm trong tam giác , , , . Tâm đường tròn ngoại tiếp của chúng lần lượt là , , , : bốn đỉnh của vùng Voronoi của điểm , là một tứ giác. Ví dụ cách cả , , đúng .
Các thuật toán dựng
| Thuật toán | Thời gian | Ghi chú |
|---|---|---|
| Thử mọi bộ ba điểm, kiểm tra đường tròn rỗng | chỉ dùng làm brute force kiểm tra | |
| Tam giác phân bất kỳ rồi lật cạnh đến khi hết cạnh xấu | lần lật | đơn giản về ý tưởng |
| Thêm điểm tăng dần (Bowyer-Watson / chèn rồi lật) | xấu nhất | thêm theo thứ tự ngẫu nhiên kèm cấu trúc định vị điểm: kỳ vọng |
| Chia để trị Guibas-Stolfi (quad-edge) | cài đặt bên dưới | |
| Fortune (quét đường, dựng thẳng Voronoi) | khó cài hơn trong phòng thi |
Thêm điểm và lật cạnh. Bắt đầu với một tam giác lớn chứa mọi điểm. Thêm từng điểm : tìm tam giác chứa , chia nó thành tam giác (hoặc nếu nằm trên cạnh), rồi kiểm tra các cạnh đối diện : cạnh nào không hợp lệ thì lật, và kiểm tra tiếp hai cạnh mới lộ ra. Mọi cạnh bị lật đều trở thành cạnh nối với . Bowyer-Watson là cùng ý tưởng nhìn theo cách khác: xóa mọi tam giác có đường tròn ngoại tiếp chứa (chúng tạo thành một "lỗ" hình sao) rồi nối với các đỉnh trên biên lỗ. Thêm theo thứ tự ngẫu nhiên thì số lần lật kỳ vọng là mỗi điểm (lập luận phân tích ngược, xem Thuật toán ngẫu nhiên), phần tốn kém còn lại là định vị tam giác chứa . Điểm yếu khi cài: tam giác bao ngoài với tọa độ hữu hạn có thể làm sai các cạnh gần bao lồi, phải xử lý ba đỉnh ảo một cách tượng trưng.
Chia để trị Guibas-Stolfi. Sắp điểm theo , chia đôi, dựng đệ quy tam giác phân Delaunay của nửa trái và nửa phải (cơ sở: điểm là một cạnh, điểm là một tam giác hoặc một chuỗi nếu thẳng hàng). Ghép hai nửa:
- Tìm tiếp tuyến chung dưới của hai bao lồi: cạnh nối một điểm của với một điểm của sao cho mọi điểm đều ở phía trên. Đây là cạnh Delaunay đầu tiên giữa hai nửa.
- "Kéo khóa" từ dưới lên: ứng viên trái là láng giềng của đầu trái của theo thứ tự góc, ứng viên phải tương tự. Trước khi dùng, xóa những cạnh cũ của (hoặc ) mà ứng viên kế tiếp nằm trong đường tròn qua và ứng viên hiện tại: các cạnh này không còn Delaunay khi có thêm điểm của nửa kia.
- Trong hai ứng viên còn hợp lệ (nằm phía trên ), chọn ứng viên mà đường tròn qua nó và không chứa ứng viên kia; nối nó với đầu mút bên kia, cạnh mới trở thành .
- Dừng khi không còn ứng viên hợp lệ: chính là tiếp tuyến chung trên.
Mỗi lần ghép xóa và thêm tổng cạnh, nên , giống chia để trị thông thường. Để duyệt "láng giềng kế tiếp theo góc" trong , cài đặt dùng cấu trúc quad-edge: mỗi cạnh có bản ghi (hai chiều của cạnh và hai chiều của cạnh đối ngẫu), mỗi bản ghi lưu onext (cạnh kế tiếp ngược chiều kim đồng hồ quanh cùng gốc); mọi phép thay đổi đều quy về một thao tác splice.
Cài đặt
Chương trình đọc điểm nguyên (có thể trùng nhau), bỏ điểm trùng (nối điểm trùng tốn ), dựng tam giác phân Delaunay bằng chia để trị, in số cạnh và các cạnh, rồi in tổng độ dài cây khung nhỏ nhất Euclid tính bằng Kruskal trên các cạnh Delaunay. Với ví dụ điểm ở trên, đầu vào
7
0 0
6 0
3 1
1 4
5 4
3 6
3 3
cho đầu ra
Delaunay edges: 13
(0,0)-(1,4)
(0,0)-(3,1)
(0,0)-(6,0)
(1,4)-(3,1)
(1,4)-(3,3)
(1,4)-(3,6)
(3,1)-(3,3)
(3,1)-(5,4)
(3,1)-(6,0)
(3,3)-(3,6)
(3,3)-(5,4)
(3,6)-(5,4)
(5,4)-(6,0)
MST: 15.625118
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
// Points sorted by (x, y), duplicates removed before triangulating
vector<ll> X, Y;
ll cross(int o, int a, int b) { // (a - o) x (b - o)
return (X[a] - X[o]) * (Y[b] - Y[o]) - (Y[a] - Y[o]) * (X[b] - X[o]);
}
// Is point p strictly inside the circumcircle of (a, b, c)? (a, b, c counter-clockwise)
// Translate so that p is the origin, then evaluate the 3x3 in-circle determinant exactly
bool inCircle(int p, int a, int b, int c) {
lll ax = X[a] - X[p], ay = Y[a] - Y[p];
lll bx = X[b] - X[p], by = Y[b] - Y[p];
lll cx = X[c] - X[p], cy = Y[c] - Y[p];
lll det = (ax * ax + ay * ay) * (bx * cy - by * cx)
+ (bx * bx + by * by) * (cx * ay - cy * ax)
+ (cx * cx + cy * cy) * (ax * by - ay * bx);
return det > 0;
}
// Quad-edge structure (Guibas-Stolfi). Each edge owns 4 records q..q+3 (q multiple of 4):
// q = edge a->b, q+2 = edge b->a, q+1 and q+3 = dual edges.
vector<int> nxt, org; // nxt[e] = onext(e), org[e] = origin point (-1 for dual records)
vector<char> alive; // alive[q / 4]
int rot(int e) { return (e & ~3) | ((e + 1) & 3); }
int invRot(int e) { return (e & ~3) | ((e + 3) & 3); }
int sym(int e) { return e ^ 2; }
int onext(int e) { return nxt[e]; }
int oprev(int e) { return rot(nxt[rot(e)]); }
int lnext(int e) { return rot(nxt[invRot(e)]); }
int dest(int e) { return org[sym(e)]; }
int makeEdge(int a, int b) {
int q = nxt.size();
nxt.insert(nxt.end(), {q, q + 3, q + 2, q + 1});
org.insert(org.end(), {a, -1, b, -1});
alive.push_back(1);
return q;
}
void splice(int a, int b) {
int al = rot(nxt[a]), be = rot(nxt[b]);
swap(nxt[a], nxt[b]);
swap(nxt[al], nxt[be]);
}
int connect(int a, int b) { // new edge dest(a) -> org(b)
int q = makeEdge(dest(a), org[b]);
splice(q, lnext(a));
splice(sym(q), b);
return q;
}
void deleteEdge(int e) {
splice(e, oprev(e));
splice(sym(e), oprev(sym(e)));
alive[e >> 2] = 0;
}
// Triangulate points l..r-1. Returns (ccw hull edge out of leftmost point,
// cw hull edge out of rightmost point)
pair<int, int> rec(int l, int r) {
int n = r - l;
if (n == 2) {
int a = makeEdge(l, l + 1);
return {a, sym(a)};
}
if (n == 3) {
int a = makeEdge(l, l + 1), b = makeEdge(l + 1, l + 2);
splice(sym(a), b);
ll side = cross(l, l + 1, l + 2);
if (side == 0) return {a, sym(b)}; // collinear: just a chain
int c = connect(b, a);
if (side > 0) return {a, sym(b)};
return {sym(c), c};
}
int mid = l + n / 2;
auto [ldo, ldi] = rec(l, mid);
auto [rdi, rdo] = rec(mid, r);
// Find the lower common tangent of the two halves
while (true) {
if (cross(org[rdi], dest(ldi), org[ldi]) < 0) ldi = lnext(ldi);
else if (cross(org[ldi], dest(rdi), org[rdi]) > 0) rdi = onext(sym(rdi));
else break;
}
int base = connect(sym(rdi), ldi);
if (org[ldi] == org[ldo]) ldo = sym(base);
if (org[rdi] == org[rdo]) rdo = base;
auto valid = [&](int e) { return cross(dest(e), dest(base), org[base]) > 0; };
// Zip the two halves together from bottom to top
while (true) {
int lc = onext(sym(base));
if (valid(lc))
while (inCircle(dest(onext(lc)), dest(base), org[base], dest(lc))) {
int t = onext(lc); deleteEdge(lc); lc = t;
}
int rc = oprev(base);
if (valid(rc))
while (inCircle(dest(oprev(rc)), dest(base), org[base], dest(rc))) {
int t = oprev(rc); deleteEdge(rc); rc = t;
}
if (!valid(lc) && !valid(rc)) break; // reached the upper tangent
if (!valid(lc) || (valid(rc) && inCircle(dest(rc), org[rc], dest(lc), org[lc])))
base = connect(rc, sym(base));
else
base = connect(sym(base), sym(lc));
}
return {ldo, rdo};
}
// Delaunay edges of distinct points (pairs of indices into the sorted X, Y)
vector<pair<int, int>> delaunayEdges() {
nxt.clear(); org.clear(); alive.clear();
int n = X.size();
if (n < 2) return {};
rec(0, n);
vector<pair<int, int>> edges;
for (int q = 0; q < (int)alive.size(); q++)
if (alive[q]) edges.push_back({org[4 * q], org[4 * q + 2]});
return edges;
}
struct DSU {
vector<int> p;
DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; p[a] = b; return true; }
};
int main() {
int n;
if (!(cin >> n)) return 0;
vector<pair<ll, ll>> pts(n);
for (auto& [x, y] : pts) cin >> x >> y;
// Sort and remove duplicates (duplicates are joined with cost 0 anyway)
vector<pair<ll, ll>> uniq = pts;
sort(uniq.begin(), uniq.end());
uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
X.clear(); Y.clear();
for (auto& [x, y] : uniq) X.push_back(x), Y.push_back(y);
vector<pair<int, int>> edges = delaunayEdges();
// Euclidean MST: Kruskal over the O(n) Delaunay edges, compare squared lengths exactly
vector<tuple<ll, int, int>> w;
for (auto [a, b] : edges) {
ll dx = X[a] - X[b], dy = Y[a] - Y[b];
w.push_back({dx * dx + dy * dy, a, b});
}
sort(w.begin(), w.end());
DSU dsu(X.size());
double total = 0;
for (auto [d, a, b] : w)
if (dsu.unite(a, b)) total += sqrt((double)d);
cout << "Delaunay edges: " << edges.size() << '\n';
vector<pair<int, int>> out;
for (auto [a, b] : edges) out.push_back({min(a, b), max(a, b)});
sort(out.begin(), out.end());
for (auto [a, b] : out)
cout << "(" << X[a] << "," << Y[a] << ")-(" << X[b] << "," << Y[b] << ")\n";
cout << fixed << setprecision(6) << "MST: " << total << '\n';
}
import sys
from math import sqrt
sys.setrecursionlimit(10000)
def delaunay_edges(X, Y):
"""Delaunay edges of distinct points sorted by (x, y). Guibas-Stolfi divide and conquer."""
nxt, org, alive = [], [], []
def cross(o, a, b):
return (X[a] - X[o]) * (Y[b] - Y[o]) - (Y[a] - Y[o]) * (X[b] - X[o])
def in_circle(p, a, b, c):
# p strictly inside circumcircle of ccw (a, b, c); Python ints are exact
ax, ay = X[a] - X[p], Y[a] - Y[p]
bx, by = X[b] - X[p], Y[b] - Y[p]
cx, cy = X[c] - X[p], Y[c] - Y[p]
det = ((ax * ax + ay * ay) * (bx * cy - by * cx)
+ (bx * bx + by * by) * (cx * ay - cy * ax)
+ (cx * cx + cy * cy) * (ax * by - ay * bx))
return det > 0
def rot(e): return (e & ~3) | ((e + 1) & 3)
def inv_rot(e): return (e & ~3) | ((e + 3) & 3)
def sym(e): return e ^ 2
def oprev(e): return rot(nxt[rot(e)])
def lnext(e): return rot(nxt[inv_rot(e)])
def dest(e): return org[e ^ 2]
def make_edge(a, b):
q = len(nxt)
nxt.extend((q, q + 3, q + 2, q + 1))
org.extend((a, -1, b, -1))
alive.append(True)
return q
def splice(a, b):
al, be = rot(nxt[a]), rot(nxt[b])
nxt[a], nxt[b] = nxt[b], nxt[a]
nxt[al], nxt[be] = nxt[be], nxt[al]
def connect(a, b):
q = make_edge(dest(a), org[b])
splice(q, lnext(a))
splice(sym(q), b)
return q
def delete_edge(e):
splice(e, oprev(e))
splice(sym(e), oprev(sym(e)))
alive[e >> 2] = False
def rec(l, r):
n = r - l
if n == 2:
a = make_edge(l, l + 1)
return a, sym(a)
if n == 3:
a, b = make_edge(l, l + 1), make_edge(l + 1, l + 2)
splice(sym(a), b)
side = cross(l, l + 1, l + 2)
if side == 0:
return a, sym(b)
c = connect(b, a)
return (a, sym(b)) if side > 0 else (sym(c), c)
mid = l + n // 2
ldo, ldi = rec(l, mid)
rdi, rdo = rec(mid, r)
while True: # lower common tangent
if cross(org[rdi], dest(ldi), org[ldi]) < 0:
ldi = lnext(ldi)
elif cross(org[ldi], dest(rdi), org[rdi]) > 0:
rdi = nxt[sym(rdi)]
else:
break
base = connect(sym(rdi), ldi)
if org[ldi] == org[ldo]:
ldo = sym(base)
if org[rdi] == org[rdo]:
rdo = base
def valid(e):
return cross(dest(e), dest(base), org[base]) > 0
while True: # zip the halves from bottom to top
lc = nxt[sym(base)]
if valid(lc):
while in_circle(dest(nxt[lc]), dest(base), org[base], dest(lc)):
t = nxt[lc]
delete_edge(lc)
lc = t
rc = oprev(base)
if valid(rc):
while in_circle(dest(oprev(rc)), dest(base), org[base], dest(rc)):
t = oprev(rc)
delete_edge(rc)
rc = t
if not valid(lc) and not valid(rc):
break
if not valid(lc) or (valid(rc) and in_circle(dest(rc), org[rc], dest(lc), org[lc])):
base = connect(rc, sym(base))
else:
base = connect(sym(base), sym(lc))
return ldo, rdo
if len(X) < 2:
return []
rec(0, len(X))
return [(org[4 * q], org[4 * q + 2]) for q in range(len(alive)) if alive[q]]
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
pts = sorted(set((int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)))
X = [p[0] for p in pts]
Y = [p[1] for p in pts]
edges = delaunay_edges(X, Y)
# Euclidean MST with Kruskal on the Delaunay edges
w = sorted(((X[a] - X[b]) ** 2 + (Y[a] - Y[b]) ** 2, a, b) for a, b in edges)
parent = list(range(len(X)))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0.0
for d, a, b in w:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
total += sqrt(d)
out = ["Delaunay edges: %d" % len(edges)]
for a, b in sorted((min(a, b), max(a, b)) for a, b in edges):
out.append("(%d,%d)-(%d,%d)" % (X[a], Y[a], X[b], Y[b]))
out.append("MST: %.6f" % total)
print("\n".join(out))
main()
Trong rec, hai cạnh trả về là cạnh bao lồi đi ra từ điểm trái nhất (theo chiều ngược kim đồng hồ) và cạnh bao lồi đi ra từ điểm phải nhất (theo chiều kim đồng hồ); bước ghép cần đúng hai cạnh này để bắt đầu tìm tiếp tuyến chung dưới. Cạnh bị xóa chỉ được đánh dấu alive = 0, cuối cùng các cạnh còn sống là tam giác phân. Muốn lấy các tam giác thay vì cạnh: với mỗi bản ghi cạnh có mặt bên trái là tam giác ( ba lần quay về và ba đỉnh ngược chiều kim đồng hồ), ghi lại bộ ba đỉnh rồi bỏ trùng.
Đã kiểm tra: bản C++ được so với brute force trên bộ test ngẫu nhiên tới điểm, gồm toàn bộ điểm thẳng hàng, điểm trên lưới (rất nhiều bộ bốn điểm cùng đường tròn) và tọa độ tới . Mỗi test kiểm tra: số cạnh đúng bằng (hoặc khi thẳng hàng), mỗi cạnh có một đường tròn rỗng đi qua (kiểm tra mỗi cạnh), không có hai cạnh cắt nhau, và dãy trọng số EMST trùng với Prim trên đồ thị đầy đủ. Bản Python cho đầu ra giống hệt bản C++ trên test ngẫu nhiên khác. Với điểm ngẫu nhiên, bản C++ chạy khoảng giây; bản Python với điểm mất vài giây.
Độ phức tạp
| Bước | Thời gian | Bộ nhớ |
|---|---|---|
| Sắp xếp và bỏ điểm trùng | ||
| Dựng Delaunay chia để trị | bản ghi như code trên, nếu tái sử dụng cạnh đã xóa | |
| Kruskal trên các cạnh Delaunay |
Vì sao cạnh. Tam giác phân là đồ thị phẳng, theo công thức Euler (xem đồ thị phẳng) nên ; chính xác hơn với là số điểm trên biên bao lồi. Mỗi cạnh tốn bản ghi quad-edge. Code trên không thu hồi cạnh đã xóa: mỗi tầng đệ quy tạo thêm cạnh nên tổng số cạnh từng được tạo là (đo được khoảng với , vẫn nhỏ). Muốn đúng bộ nhớ thì giữ một danh sách bản ghi trống và tái sử dụng khi makeEdge.
Vì sao ghép là . Mỗi vòng lặp ghép hoặc xóa một cạnh cũ, hoặc thêm một cạnh nối hai nửa. Số cạnh nối hai nửa không vượt quá số cạnh của tam giác phân kết quả, số cạnh xóa không vượt quá số cạnh của hai nửa, đều . Tìm tiếp tuyến dưới cũng chỉ đi dọc bao lồi, .
So với cách ngây thơ. Prim trên đồ thị đầy đủ là thời gian, bộ nhớ: đủ cho nhưng không cho . Kruskal trên mọi cặp là và bộ nhớ.
⚠️ Lỗi thường gặp
- Tràn số trong phép thử in-circle. Định thức là bậc theo tọa độ. Với , bình phương độ dài đã cỡ , nhân thêm một tích có ngoài là vượt
long long. Phải dời gốc về rồi tính bằng__int128. Ngay cả__int128(tối đa khoảng ) cũng chỉ an toàn chắc chắn khi hiệu tọa độ không quá khoảng (tọa độ trong ); với tọa độ lớn hơn, chia định thức thành tổng các tích rồi so sánh từng phần hoặc dùng số lớn. Dùngdoublecho phép thử này thì gặp bốn điểm gần cùng đường tròn sẽ cho tam giác phân sai, thậm chí vòng lặp vô hạn. - Điểm trùng nhau. Thuật toán giả sử các điểm đôi một khác nhau; hai điểm trùng tạo cạnh độ dài và làm hỏng các phép thử hướng. Luôn sắp xếp và
uniquetrước. Với bài cây khung, các điểm trùng nối với nhau tốn , nên chỉ cần làm việc trên tập điểm phân biệt. - Mọi điểm thẳng hàng. Khi đó không có tam giác nào; tam giác phân suy biến thành một chuỗi cạnh. Code trả về tam giác (như nhiều bản mẫu) sẽ trả về rỗng, và nếu dựng EMST từ tam giác sẽ thiếu cạnh. Hãy lấy cạnh trực tiếp từ cấu trúc quad-edge như trên, hoặc xử lý riêng trường hợp thẳng hàng.
- Bốn điểm cùng đường tròn. Khi đó tam giác phân Delaunay không duy nhất (hình vuông có hai đường chéo đều hợp lệ). Đừng so sánh danh sách cạnh với một lời giải khác để kiểm tra; hãy kiểm tra tính chất (đường tròn rỗng, số cạnh, EMST). Phép thử phải dùng
> 0nghiêm ngặt: dùng>= 0với điểm cùng đường tròn có thể xóa mãi các cạnh. - Sai chiều ba điểm. Dấu của định thức đảo khi xếp cùng chiều kim đồng hồ. Khi tự viết thuật toán lật cạnh, hãy chuẩn hóa mọi tam giác về ngược chiều kim đồng hồ trước khi gọi phép thử.
- Áp dụng cho khoảng cách khác Euclid. Tính chất "Delaunay chứa MST" chỉ đúng cho khoảng cách Euclid (và mọi hàm tăng của nó, như bình phương khoảng cách). Với khoảng cách Manhattan hay Chebyshev, cần kỹ thuật riêng (chia góc, xem khoảng cách Manhattan).
- Tưởng nhỏ cũng cần Delaunay. Với , Prim không cần lưu cạnh ngắn gọn và an toàn hơn nhiều. Chỉ dùng Delaunay khi cỡ trở lên.
Biến thể / Mở rộng
- Cây khung nhỏ nhất Euclid và các bài liên quan. Sau khi có cạnh Delaunay, mọi câu hỏi về MST đều quy về cây khung nhỏ nhất trên đồ thị thưa: đường đi minimax giữa hai điểm, phân cụm thành nhóm sao cho khoảng cách nhỏ nhất giữa hai nhóm lớn nhất (bỏ cạnh MST dài nhất), cây Kruskal tái dựng. Nếu đề cho thêm một số cạnh có sẵn (trọng số ), chỉ cần chạy Kruskal trên hợp của chúng với các cạnh Delaunay.
- Cặp điểm gần nhất và láng giềng gần nhất. Mỗi điểm có láng giềng gần nhất nằm trong các láng giềng Delaunay của nó, nên duyệt các cạnh Delaunay là đủ để tìm láng giềng gần nhất của mọi điểm trong . Chỉ cần một cặp gần nhất thì chia để trị hoặc quét đường đơn giản hơn.
- Dựng vùng Voronoi. Vùng của là giao các nửa mặt phẳng (phía của trung trực chứa ). Cách trực tiếp: lấy một khung chữ nhật đủ lớn rồi cắt lần lượt bởi trung trực của với mọi điểm khác bằng Sutherland-Hodgman, lần cắt cho một vùng, cho cả sơ đồ khi số cạnh mỗi vùng nhỏ. Nhanh hơn: chỉ cắt bởi trung trực với các láng giềng Delaunay của , hoặc đọc thẳng các đỉnh Voronoi là tâm đường tròn ngoại tiếp các tam giác quanh như ví dụ trên. Các ứng dụng điển hình: điểm xa các trạm nhất (đường tròn rỗng lớn nhất có tâm trong một đa giác: tâm là một đỉnh Voronoi hoặc giao của cạnh Voronoi với biên), phân vùng phục vụ của các trạm.
- Bao lồi 3D. Theo phép nâng lên paraboloid, Delaunay là mặt dưới bao lồi của các điểm ; thư viện bao lồi 3D có sẵn có thể dùng thay.
- Thuật toán Fortune. Dựng thẳng sơ đồ Voronoi bằng quét đường với "đường bờ biển" gồm các cung parabol, ; hay gặp trong tài liệu nhưng ít khi đáng cài trong phòng thi.
Bài tập luyện
Kho bài CTOJ hiện chưa có bài nào bắt buộc phải dựng tam giác phân Delaunay; các bài dưới đây là những bài cây khung nhỏ nhất Euclid và cặp điểm gần nhất, nơi Delaunay là một lời giải đúng (với nhỏ thì cách cũng qua).
- Lắp hệ thống điện (dhbb23cvahn11_b): (Trung bình) Cây khung nhỏ nhất Euclid khi đã có sẵn một số dây (cạnh trọng số ); nên Prim là đủ, Kruskal trên dây có sẵn cộng các cạnh Delaunay cũng cho đúng đáp án.
- Mạng Lưới Bò (moonetw): (Khó) Cây khung nhỏ nhất với chi phí là bình phương khoảng cách, ; bình phương là hàm tăng nên MST trùng EMST và Kruskal trên cạnh Delaunay giải trực tiếp (lời giải chính thức khai thác , đồng thời là test tốt cho nhiều điểm thẳng hàng và điểm trùng).
- Cặp điểm gần nhất (closept): (Rất khó) Cặp gần nhất luôn là một cạnh Delaunay, nên lấy cạnh ngắn nhất là xong; lưu ý tọa độ tới sát giới hạn
__int128của phép thử in-circle, lời giải chia để trị chuẩn an toàn hơn. - Cạnh tranh thân thiện (icpcwf24_f): (Rất khó) Chia điểm thành hai đội bằng nhau sao cho khoảng cách gần nhất giữa hai đội lớn nhất; các thành phần khi bỏ cạnh dài là thành phần của EMST, kết hợp tổng tập con.
Bình luận