Wiki › Thuật toán › Hình học tính toán › Tam giác phân Delaunay và sơ đồ Voronoi

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.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 27 phút 3 lượt xem

Cho n điểm trên mặt phẳng. Sơ đồ Voronoi (Voronoi diagram) chia mặt phẳng thành n vùng, vùng của điểm p gồm mọi vị trí gần p 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á 3n−6 cạnh, dựng được trong O(nlogn), 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 đủ n điểm (có n(n−1)2 cạnh) giảm từ O(n2) xuống O(nlogn): chạy Kruskal trên O(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 ab là một cạnh Delaunay khi và chỉ khi tồn tại một đường tròn đi qua a và b mà bên trong không có điểm nào.

Vì sao đối ngẫu với Voronoi. Tâm O của đường tròn rỗng đi qua a,b,c cách đều ba điểm này và mọi điểm khác ở xa O hơn (vì nằm ngoài đường tròn). Vậy O là điểm thuộc cả ba vùng Voronoi của a,b,c: đó chính là một đỉnh Voronoi. Tương tự, nếu có đường tròn rỗng qua a,b 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 p vùng (cell) của p
cạnh ab cạnh Voronoi, nằm trên trung trực của ab
tam giác abc đỉnh Voronoi = tâm đường tròn ngoại tiếp abc
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 ab của cây khung nhỏ nhất Euclid. Xét đường tròn đường kính ab. Nếu có điểm c nằm trong đường tròn đó thì góc acb>90∘, nên |ac|<|ab| và |bc|<|ab|. Bỏ cạnh ab khỏi cây, cây tách thành hai phần, c nằm ở một phần; nối c với đầu mút ở phần kia bằng cạnh ngắn hơn |ab| cho cây nhẹ hơn, mâu thuẫn. Vậy đường tròn đường kính ab rỗng, và ab 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á |ab|" 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 b gần a nhất thì đường tròn đường kính ab (thậm chí đường tròn tâm a bán kính |ab|) 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 a,b,c xếp ngược chiều kim đồng hồ và điểm p, dời gốc tọa độ về p (đặt a′=a−p, ...) rồi tính

det=|a′|2(b′×c′)+|b′|2(c′×a′)+|c′|2(a′×b′).

det>0 khi p nằm trong đường tròn ngoại tiếp abc, det=0 khi nằm trên, det<0 khi nằm ngoài. Đây là định thức 3×3 quen thuộc với các hàng (x′,y′,x′2+y′2): nâng mỗi điểm lên paraboloid z=x2+y2, khi đó "p trong đường tròn qua a,b,c" tương đương "p 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 4 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 ac tạo thành tứ giác lồi abcd. Nếu d nằm trong đường tròn ngoại tiếp abc thì cạnh ac là không hợp lệ; thay nó bằng đường chéo kia bd 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 P=(0,0), Q=(4,−1), R=(8,0), S=(4,1). Tam giác phân dùng đường chéo dài PR:

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ử S với đường tròn ngoại tiếp tam giác PQR (ngược chiều kim đồng hồ). Dời gốc về S: a′=P−S=(−4,−1), b′=Q−S=(0,−2), c′=R−S=(4,−1), nên |a′|2=17, |b′|2=4, |c′|2=17 và b′×c′=8, c′×a′=−8, a′×b′=8:

det=17·8+4·(−8)+17·8=240>0.

S nằm trong đường tròn (đường tròn qua P,Q,R có tâm (4;7,5), bán kính 8,5, còn S chỉ cách tâm 6,5), nên PR không hợp lệ. Lật sang đường chéo QS:

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ử P với tam giác QRS cho det=17·8+64·(−8)+17·8=−240<0, P ở ngoài; theo đối xứng R cũng ở ngoài đường tròn QSP. 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 7 điểm. Đánh số các điểm theo thứ tự (x,y) tăng dần:

đỉnh 1 2 3 4 5 6 7
tọa độ (0,0) (1,4) (3,1) (3,3) (3,6) (5,4) (6,0)

Bao lồi có h=5 đỉnh (1,7,6,5,2), nên mọi tam giác phân của tập này có đúng 3n−3−h=21−3−5=13 cạnh và 2n−2−h=7 tam giác. Tam giác phân Delaunay (chương trình bên dưới in ra đúng 13 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 13 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 d2 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ỏ (5 và 6 đã nối qua 2,4)
4-5 9 bỏ
1-3 10 nhận
3-7 10 nhận, đủ 6 cạnh

Tổng độ dài 2+5+5+8+10+10≈15,625118.

Vùng Voronoi của đỉnh 4. Đỉnh 4=(3,3) có 4 láng giềng Delaunay 2,3,5,6 và nằm trong 4 tam giác (2,3,4), (3,6,4), (4,6,5), (2,4,5). Tâm đường tròn ngoại tiếp của chúng lần lượt là (54,2), (194,2), (72,92), (52,92): bốn đỉnh của vùng Voronoi của điểm 4, là một tứ giác. Ví dụ (54,2) cách cả (1,4), (3,1), (3,3) đúng 65/4.

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 O(n4) 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 O(n2) 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) O(n2) 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 O(nlogn)
Chia để trị Guibas-Stolfi (quad-edge) O(nlogn) cài đặt bên dưới
Fortune (quét đường, dựng thẳng Voronoi) O(nlogn) 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 p: tìm tam giác chứa p, chia nó thành 3 tam giác (hoặc 4 nếu p nằm trên cạnh), rồi kiểm tra các cạnh đối diện p: 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 p. 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 p (chúng tạo thành một "lỗ" hình sao) rồi nối p 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à O(1) 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 p. Đ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 (x,y), chia đôi, dựng đệ quy tam giác phân Delaunay của nửa trái L và nửa phải R (cơ sở: 2 điểm là một cạnh, 3 đ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:

  1. Tìm tiếp tuyến chung dưới của hai bao lồi: cạnh base nối một điểm của L với một điểm của R sao cho mọi điểm đều ở phía trên. Đây là cạnh Delaunay đầu tiên giữa hai nửa.
  2. "Kéo khóa" từ dưới lên: ứng viên trái lc là láng giềng của đầu trái của base theo thứ tự góc, ứng viên phải rc tương tự. Trước khi dùng, xóa những cạnh cũ của L (hoặc R) mà ứng viên kế tiếp nằm trong đường tròn qua base 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.
  3. Trong hai ứng viên còn hợp lệ (nằm phía trên base), chọn ứng viên mà đường tròn qua nó và base 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 base.
  4. Dừng khi không còn ứng viên hợp lệ: base chính là tiếp tuyến chung trên.

Mỗi lần ghép xóa và thêm tổng O(n) cạnh, nên T(n)=2T(n/2)+O(n)=O(nlogn), giống chia để trị thông thường. Để duyệt "láng giềng kế tiếp theo góc" trong O(1), cài đặt dùng cấu trúc quad-edge: mỗi cạnh có 4 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 n điểm nguyên (có thể trùng nhau), bỏ điểm trùng (nối điểm trùng tốn 0), 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ụ 7 đ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
C++
#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';
}
Python
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 e có mặt bên trái là tam giác (lnext ba lần quay về e 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 6000 bộ test ngẫu nhiên tới 60 điểm, gồm toàn bộ điểm thẳng hàng, điểm trên lưới 5×5 (rất nhiều bộ bốn điểm cùng đường tròn) và tọa độ tới 5·108. Mỗi test kiểm tra: số cạnh đúng bằng 3n−3−h (hoặc n−1 khi thẳng hàng), mỗi cạnh có một đường tròn rỗng đi qua (kiểm tra O(n2) 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 O(n2) trên đồ thị đầy đủ. Bản Python cho đầu ra giống hệt bản C++ trên 500 test ngẫu nhiên khác. Với n=2·105 điểm ngẫu nhiên, bản C++ chạy khoảng 0,2 giây; bản Python với 105 đ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 O(nlogn) O(n)
Dựng Delaunay chia để trị O(nlogn) O(nlogn) bản ghi như code trên, O(n) nếu tái sử dụng cạnh đã xóa
Kruskal trên các cạnh Delaunay O(nlogn) O(n)

Vì sao O(n) cạnh. Tam giác phân là đồ thị phẳng, theo công thức Euler V−E+F=2 (xem đồ thị phẳng) nên E≤3n−6; chính xác hơn E=3n−3−h với h là số điểm trên biên bao lồi. Mỗi cạnh tốn 4 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 O(n) cạnh nên tổng số cạnh từng được tạo là O(nlogn) (đo được khoảng 10n với n=2·105, vẫn nhỏ). Muốn đúng O(n) 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à O(n). 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 O(n). Tìm tiếp tuyến dưới cũng chỉ đi dọc bao lồi, O(n).

So với cách ngây thơ. Prim trên đồ thị đầy đủ là O(n2) thời gian, O(n) bộ nhớ: đủ cho n≤5000 nhưng không cho n=105. Kruskal trên mọi cặp là O(n2logn) và O(n2) bộ nhớ.

⚠️ Lỗi thường gặp

  • Tràn số trong phép thử in-circle. Định thức là bậc 4 theo tọa độ. Với |x|,|y|≤109, bình phương độ dài đã cỡ 8·1018, nhân thêm một tích có ngoài là vượt long long. Phải dời gốc về p rồi tính bằng __int128. Ngay cả __int128 (tối đa khoảng 1,7·1038) cũng chỉ an toàn chắc chắn khi hiệu tọa độ không quá khoảng 109 (tọa độ trong [−5·108,5·108]); 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ùng double cho 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 0 và làm hỏng các phép thử hướng. Luôn sắp xếp và unique trước. Với bài cây khung, các điểm trùng nối với nhau tốn 0, 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 n−1 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 > 0 nghiêm ngặt: dùng >= 0 vớ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 a,b,c 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 8 góc, xem khoảng cách Manhattan).
  • Tưởng n nhỏ cũng cần Delaunay. Với n≤5000, Prim O(n2) 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 n cỡ 105 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ó O(n) 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 k nhóm sao cho khoảng cách nhỏ nhất giữa hai nhóm lớn nhất (bỏ k−1 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ố 0), 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 O(n). 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 p là giao các nửa mặt phẳng {x:|x−p|≤|x−q|} (phía của trung trực pq chứa p). 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 p với mọi điểm khác bằng Sutherland-Hodgman, O(n) lần cắt cho một vùng, O(n2) 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 p, 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 p 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 (x,y,x2+y2); 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, O(nlogn); 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 n nhỏ thì cách O(n2) 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ố 0); n≤1000 nên Prim O(n2) 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, N=105; 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 y≤10, đồ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 109 sát giới hạn __int128 củ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 2n đ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.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0