ผลต่างระหว่างรุ่นของ "โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม"

 

==== รหัสเทียม ====

=== ความซับซ้อนในการคำนวณ ===

โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า O (n log n) ได้หรือไม่ ในปี 1990 นั้น [[David G. Kirkpatrick]],[[ Maria M. Klawe]], [[Robert E. Tarjan]] ได้ค้นพบอัลกอริทึมที่ใช้เวลาเพียง O (n log log n) สำหรับวิธีใช้อัลกอริทึมแบบสุ่มนั้นเช่นอัลกอริทึมของ [[Seidel's]] or [[Clarkson et al.'s]], ใช้เวลาเป็น O (n log* n) ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ O (n) เลย <br /> <br />