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_i trên bao lồi, ta cần tìm p_i+1 = f(p_i,P) sao cho mọi điểm trong P đều nằm bên phải đường thẳng p_i p_i+1. 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_i,Q) trong thời gian O(log m) bằng tìm kiếm nhị phân. Có thể tìm f(p_i,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_i,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_i,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

• Timothy M. Chan (1996), “Optimal output-sensitive convex hull algorithms in two and three dimensions”, Discrete and Computational Geometry, 16: 361–368