Thuật toán Chan

Trong hình học tính toán, **thuật toán Chan**, gọi theo tên của Timothy M. Chan, là một thuật toán phụ thuộc dữ liệu ra tối ưu cho việc tìm bao lồi của tập hợp *P* gồm *n* điểm trong không gian 2 hoặc 3 chiều. Thuật toán chạy trong thời gian O(*n* log *h*), trong đó *h* là số đỉnh của bao lồi. Trong trường hợp không gian 2 chiều, thuật toán là sự kết hợp giữa một thuật toán tìm bao lồi trong thời gian O(*n* log *n*) (chẳng hạn quét Graham) với thuật toán bọc gói, để thu được thời gian tối ưu là O(*n* log *h*). Thuật toán Chan đáng chú ý vì nó đơn giản hơn nhiều so với thuật toán bao lồi phẳng cuối cùng, và nó mở rộng một cách tự nhiên lên không gian 3 chiều.

## Thuật toán
Trước tiên, giả sử ta đã biết *h* và đặt tham số *m*=*h*. Giả thuyết này là không thực tế và ta sẽ loại bỏ nó sau này. Đầu tiên, thuật toán chia tập hợp *P* một cách tùy ý thành  1+*n*/*m* tập hợp con *Q*, mỗi tập chứa  *m* điểm. Sau đó, tìm bao lồi của mỗi tập *Q* bằng thuật toán chạy trong thời gian O(*n* log *n*). Nhận thấy rằng có O(*n*/*m*) tập hợp con, mỗi tập gồm O(*m*) điểm, nên giai đoạn này tốn thời gian O(*n/m*)O(*m* log *m*) = O(*n* log *m*).

Giai đoạn thứ hai là thực hiện thuật toán bọc gói sử dụng những bao lồi đã tìm ra ở giai đoạn trước để tăng tốc độ. Trong mỗi bước của thuật toán bọc gói, với mỗi điểm *p<sub>i</sub>* trên bao lồi, ta cần tìm pi+1 = *f(p<sub>i</sub>,P)* sao cho mọi điểm trong *P* đều nằm bên phải đường thẳng *p<sub>i</sub> p<sub>i+1</sub>*. Nếu ta đã biết bao lồi của tập hợp *Q* gồm *m* điểm, thì có thể tìm *f(p<sub>i</sub>,Q)* trong thời gian O(log *m*) bằng tìm kiếm nhị phân. Có thể tìm *f(p<sub>i</sub>,Q)* cho tất cả O(*n*/*m*) tập hợp con *Q* trong thời gian O(*n*/*m* log *m*) Do đó có thể tìm *f(p<sub>i</sub>,P)* tương tự như trong thuật toán bọc gói thông thường nhưng chỉ cần xem xét các điểm *f(p<sub>i</sub>,Q)* cho mọi tập hợp con *Q*. Do thuật toán bọc gói lặp lại bước trên O(*h*) lần, giai đoạn hai tốn thời gian O(*n* log *m*), và nếu *m=h*, thì thời gian đó đúng bằng O(*n* log *h*).

Bằng cách thực hiện hai giai đoạn trên, có thể tìm bao lồi của *n* điểm trong thời gian O(*n* log *h*), giả sử ta đã biết trước *h*. Nếu ta chọn *m<h*, thì có thể dừng thuật toán sau *m*+1 bước, nên chỉ cần dùng thời gian O(*n* log *m*) (nhưng không tìm được bao lồi). Ý tưởng chính ở đây là khởi tạo *m* là một hằng số nhỏ (ta dùng 2 cho phân tích dưới đây nhưng trên thực tế một hằng số bằng khoảng 5 hoạt động tốt hơn), và tăng giá trị *m* cho tới khi *m>h*, và khi đó ta tìm được bao lồi.

Nếu tăng giá trị *m* quá chậm thì khoảng thời gian bị bỏ phí khi *m<h* có thể quá lớn. Trong khi đó nếu tăng *m* quá nhanh, ta có thể làm *m* lớn hơn *h* rất nhiều, và do đó cũng làm tăng thời gian thực thi. Thuật toán Chan bình phương giá trị của *m* sau mỗi lần lặp và đảm bảo giá trị *m* không bao giờ vượt quá *n*. Nói cách khác, sau *t* lần lặp, ta có m = \min(n,2^{2^t}). Tổng thời gian thực thi của thuật toán là

 \sum_{t=0}^{O(\log\log h)} O\left(n \log(2^{2^t})\right) = O(n) \sum_{t=0}^{O(\log\log h)} O(2^t) = O\left(n \cdot 2^{1+O(\log\log h)}\right) = O(n \log h).

Để tổng quát hóa lên 3 chiều cần sử dụng một thuật toán tìm bao lồi trong không gian 3 chiều trong thời gian O(*n* log *n*) thay vì quét Graham cho 2 chiều, và một phiên bản 3 chiều của thuật toán bọc gói. Thời gian thực thi vẫn là O(*n* log *h*).

## Lập trình

Bài báo của Chan cũng có một số gợi ý để cải thiện tốc độ thuật toán trong thực tế, ví dụ:

* Sau mỗi lần tìm các bao lồi của các tập con, loại bỏ các điểm không nằm trên bao lồi trong những lần lặp sau.
* Có thể tìm bao lồi của tập hợp lớn bằng cách hợp bao lồi các tập hợp con thay vì tính lại từ đầu.

## Tham khảo
*