Bài toán yêu cầu tìm một phép tam giác hóa của tập điểm đã cho mà chứa hai cạnh cụ thể. Nhiều lập luận dưới đây được nhắc tới trong bài viết được liên kết ở bản phân tích chính thức; có thể dùng bài viết ấy làm phần nhập môn.

Bước đầu tiên là nhận ra một số tính chất của công việc đã hoàn thiện. Gọi \(P\) là tập cọc đầu vào, và \(F\) là một tập lớn nhất các hàng rào có đầu mút thuộc \(P\) mà không giao nhau ngoài các đầu mút.

1. Các cạnh của bao lồi của \(P\) đều thuộc \(F\). Theo định nghĩa, các cạnh bao lồi không giao với bất kỳ hàng rào khả dĩ nào khác. Vì vậy, ta có thể thêm chúng vào mọi tập hàng rào chưa chứa chúng mà không tạo giao cắt không hợp lệ; do đó mọi tập lớn nhất đều chứa tất cả các cạnh ấy.

2. \(|F|\le3N-3-c\), trong đó \(c\) là số đỉnh của bao lồi của \(P\). Xét đồ thị mà các cọc là đỉnh và các hàng rào trong \(F\) là cạnh. Đây là đồ thị phẳng nên áp dụng được dạng tổng quát của công thức Euler:

$\(N+A=K+|F|,\)$

trong đó \(A\) là số miền trong (không tính miền ngoài), còn \(K\) là số thành phần liên thông.

Mỗi cạnh trên bao lồi kề đúng một miền trong, còn mỗi cạnh khác kề nhiều nhất hai miền trong. Tổng số cạnh biên của mọi miền trong ít nhất là \(3A\); phép đếm đó tính mỗi cạnh bao lồi một lần và mỗi cạnh khác nhiều nhất hai lần. Bởi vậy

$\(3A\le c+2(|F|-c)=2|F|-c,\)$

nên \(A\le(2|F|-c)/3\). Thế vào công thức Euler, ta có

$\(N+(2|F|-c)/3\ge K+|F|.\)$

Suy ra \(3N+2|F|-c\ge3K+3|F|\), rồi \(3N-c-3K\ge|F|\). Vì \(K\ge1\), ta thu được \(|F|\le3N-3-c\).

1. \(|F|\ge3N-3-c\). Ta chứng minh bằng quy nạp. Trường hợp cơ sở là mọi điểm trong \(P\) đều nằm trên bao lồi. Khi đó, lấy toàn bộ cạnh của bao lồi cùng với một phép tam giác hóa bất kỳ của \(P\). Tập này có đúng \(2N-3\) cạnh, bằng \(3N-3-c\) khi \(N=c\), chứng minh tồn tại một tập ít nhất lớn như vậy mà không có giao cắt không hợp lệ.

Nếu tồn tại điểm \(p\) không nằm trên bao lồi của \(P\), xét một tập cạnh tối ưu cho \(P\setminus\{p\}\). Theo giả thuyết quy nạp, tập đó có kích thước \(3(N-1)-3-c\). Vì \(|F|=3(N-1)-c-3\) và từ mục (2) có \(3(N-1)-c-3K\ge|F|\), số thành phần liên thông \(K\) buộc phải bằng đúng \(1\). Tương tự, mọi miền trong phải là tam giác; mỗi cạnh bao lồi kề một miền và mỗi cạnh không thuộc bao lồi kề hai miền.

Theo định nghĩa, \(p\) không thuộc bao lồi. Do không có ba điểm thẳng hàng, \(p\) cũng không nằm trên một cạnh có sẵn. Vậy \(p\) nằm nghiêm ngặt bên trong một trong các tam giác ấy. Nối \(p\) với cả ba đỉnh của tam giác chứa nó, ta được một lời giải kích thước

$\(3(N-1)-3-c+3=3N-3-c.\)$

Từ (2) và (3), ta biết chính xác số hàng rào cần xây khi biết kích thước bao lồi của tập cọc. Hơn nữa, một đáp án như vậy chứa bao lồi của \(P\), và mọi miền trong được các hàng rào output bao quanh đều là tam giác. Ta có thể dùng các tính chất này để xây dựng thuật toán sinh tập tối ưu.

Phân nhóm 1

Có nhiều lời giải cho Phân nhóm 1. Chẳng hạn, quy trình trong chứng minh mục (3) cho biết cách giải khi không có hàng rào đặt trước. Có những cách xử lý riêng các hàng rào đặt trước, nhưng chúng cần khá nhiều công sức; ta có một cách đơn giản hơn.

Các chứng minh trên cho thấy mọi tập hàng rào cực đại cũng là lớn nhất (lưu ý rằng trong lập luận, ta chỉ dùng tính cực đại). Do đó, chỉ cần liên tục thêm hàng rào miễn là nó không giao với hàng rào nào đã thêm. Cách này xử lý hàng rào đặt trước rất dễ: khởi tạo tập bằng chính hai hàng rào đó. Có \(O(N^2)\) hàng rào tiềm năng; với mỗi hàng rào, cần kiểm tra nó có giao với hàng rào nào đang có hay không. Vì toàn bộ lời giải có kích thước \(O(N)\), ta thực hiện \(O(N^3)\) phép kiểm tra giao nhau. Kiểm tra hai đoạn thẳng có giao nhau hay không mất thời gian hằng số, nên tổng thời gian là \(O(N^3)\).

Phân nhóm 2

Giống Phân nhóm 1, có nhiều thuật toán giải bài khi bỏ qua hai hàng rào đặt trước, nhưng chỉ một số dễ điều chỉnh cho chúng. Ví dụ, có thể cài đặt hiệu quả quy trình trong chứng minh mục (3): nếu thứ tự xử lý điểm được ngẫu nhiên hóa và ta lưu các tam giác hiện tại trong một cấu trúc dạng cây để tìm tam giác hiệu quả, độ phức tạp kỳ vọng là \(O(N\log N)\). Thuật toán thu được tương tự thuật toán tăng dần để tính phép tam giác hóa Delaunay.

Một lựa chọn khác là sửa thuật toán Graham Scan tìm bao lồi: ngoài bao lồi của các điểm đã thăm, ta còn duy trì toàn bộ tam giác của những điểm nằm bên trong nó.

Đáng tiếc, dù các thuật toán trên có thể xử lý hai hàng rào đặt trước bằng nhiều mã xử lý riêng, chúng trở nên rất cồng kềnh. Sau đây là một số phương án tốt hơn.

Gọi \(x\) là giao điểm của hai đường thẳng vô hạn kéo dài từ hai hàng rào đặt trước. Vì hai hàng rào không giao nhau, \(x\) có thể nằm trên một trong hai hàng rào nhưng không thể nằm trên cả hai. Gọi một hàng rào đặt trước không chứa \(x\) là \(f_1\), và hàng rào kia là \(f_2\). Theo định nghĩa, toàn bộ \(f_2\) nằm về cùng một phía của đường thẳng kéo dài \(f_1\). Ta nhận biết hàng rào nào có thể là \(f_1\) bằng cách so sánh hướng của hai đầu mút của ứng viên \(f_1\) với từng đầu mút của \(f_2\) — tức kiểm tra cả hai đầu mút của ứng viên \(f_2\) có nằm cùng phía đường thẳng qua \(f_1\) hay không.

Quét đường thẳng

Khi không có hàng rào đặt trước, ta có thể dùng quét đường thẳng: xét các điểm theo thứ tự tọa độ X và duy trì bao lồi của mọi điểm đã thấy, giống thuật toán bao lồi monotone chain. Khi xét điểm mới \(p\), ta nối nó với mọi điểm trong tập đã thấy mà đoạn nối từ \(p\) không gây giao cắt. Những điểm này tạo thành một đoạn liên tục trên phía bên phải của bao lồi của tập đã thấy. Vì vậy, ta có thể tìm chúng hiệu quả bằng tìm kiếm tam phân trên phía bên phải ấy.

Để xử lý các hàng rào đặt trước, trước tiên xoay mặt phẳng để \(f_2\) thẳng đứng (có thể co giãn mọi thứ để chỉ dùng số nguyên), rồi chỉ chạy thuật toán quét trên những điểm nằm cùng phía với \(f_2\) so với đường thẳng đi qua \(f_1\); tập này chứa cả hai đầu mút \(f_2\) và không chứa đầu mút nào của \(f_1\). Vì giờ \(f_2\) thẳng đứng, thuật toán sẽ tự thêm nó vào tập khi xử lý đầu mút thứ hai. Sau đó, ta lại xoay mọi thứ để \(f_1\) thẳng đứng, rồi bắt đầu thuật toán từ tập và bao lồi đã có (hai đầu mút của \(f_1\) là hai điểm đầu tiên được xử lý trong lượt hai). Như trước, thuật toán sẽ tự thêm \(f_1\).

Việc điều chỉnh để xử lý hàng rào đặt trước chỉ tốn thời gian tuyến tính, nên giống phiên bản không có chúng, toàn bộ thuật toán mất \(O(N\log N)\) thời gian.

Chia để trị

Thuật toán chia để trị này cũng có một phiên bản tương ứng trong bài toán tính bao lồi. Ý tưởng đơn giản: chia tập điểm bằng một đường thẳng đi qua hai điểm, tính kết quả ở mỗi phía (cả hai phía đều bao gồm hai điểm đó), rồi hợp nhất.

Gọi hai kết quả đệ quy là \(P\) và \(Q\). Bao lồi của chúng là hai đa giác lồi có chung một cạnh. Ta duy trì hai cọc hiện tại \(p,q\). Ban đầu cả hai cùng ở một đầu mút của cạnh chung. Cả hai di chuyển ra xa cạnh chung: \(p\) đi qua các đỉnh liên tiếp của \(P\), còn \(q\) đi qua các đỉnh liên tiếp của \(Q\). Lúc đầu, ta di chuyển cả hai cùng nhau. Sau đó, gọi \(p_0,q_0\) lần lượt là vị trí trước đó của \(p,q\), còn \(p_1,q_1\) là giá trị kế tiếp của mỗi cọc (nghĩa là \(p_0p\) và \(pp_1\) là hai cạnh kề nhau trên bao lồi của \(P\), còn \(q_0q\) và \(qq_1\) là hai cạnh kề nhau trên bao lồi của \(Q\)). Khi ấy:

• Nếu \(p_1q\) không giao \(p_0p\), đặt \(p=p_1\).
• Nếu \(q_1p\) không giao \(q_0q\), đặt \(q=q_1\).
• Nếu không, dừng lại.

Mỗi lần di chuyển một cọc, ta thêm hàng rào nối \(p\) và \(q\) hiện tại vào kết quả. Khi hoàn tất, ta làm tương tự từ đầu mút còn lại của cạnh chung.

Để chia đều, ta có thể chọn một điểm \(x\) bất kỳ, sắp xếp các điểm khác theo góc, chọn điểm trung vị làm \(y\), rồi chia bằng đường thẳng qua \(x,y\). Hoặc ta có thể chọn điểm ngẫu nhiên. Trung bình, phép chia sẽ gần cân bằng (giống lời giải đề xuất cho bài Juggle Struggle: Part 1).

Công việc hợp nhất mất thời gian tuyến tính; việc chia mất \(O(N\log N)\) với phiên bản sắp xếp hoặc thời gian tuyến tính với phiên bản ngẫu nhiên. Theo định lý Master, phiên bản ngẫu nhiên có tổng độ phức tạp \(O(N\log N)\), còn phiên bản sắp xếp có tổng thời gian \(O(N\log^2 N)\).

Nguồn

Google Code Jam 2021, Vòng 3, bài Fence Design.

Phân tích chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.