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.