Có một thuật toán cho tam giác đa giác theo thời gian tuyến tính do Chazelle (1991), nhưng AFAIK không có bất kỳ sự triển khai chuẩn nào của thuật toán trong các thư viện phần mềm toán học nói chung. Có ai biết về một thực hiện như vậy mà tôi không thể tìm thấy bởi Googling?Thực hiện thuật toán tam giác của Chazelle
Xem này answer to "Powerful Algorithms too complex to implement":
Theo Skienna (tác giả của The Algorithm Design Manual), "[các] thuật toán là khá vô vọng để thực hiện."
Tôi đã tìm cách triển khai trước đó, nhưng không thể tìm thấy. Tôi nghĩ rằng nó an toàn để giả định không ai thực hiện nó do sự phức tạp của nó, và tôi nghĩ rằng nó cũng có một yếu tố không đổi khá lớn nên sẽ không làm tốt với các thuật toán O(n lg n) có các yếu tố không đổi nhỏ hơn.