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

 
=== ความซับซ้อนในการคำนวณ ===
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า <math>O (n log n)</math> ได้หรือไม่ ในปี 1990 นั้น [[:en:David G. Kirkpatrick|David G. Kirkpatrick]],[[:en:David MariaG. MKirkpatrick|David G. KlaweKirkpatrick]], [[:en:Robert E. Tarjan|Robert E. Tarjan]] ได้ค้นพบอัลกอริทึมที่ใช้เวลาเพียง <math>O (n log log n)</math> สำหรับวิธีใช้อัลกอริทึมแบบสุ่มนั้นเช่นอัลกอริทึมของ [[:en:Seidel's|Seidel's]] or [[:en:Clarkson et al.'s|Clarkson et al.'s]], ใช้เวลาเป็น <math>O (n log* n)</math> ซึ่งในความเป็นจริงแล้วแทบไม่ต่างอะไรกับ <math>O (n) เลย <br /math> <br />เลย
 
นอกจากวิธีการข้างต้นแล้ว [[:en:Bernard Chazelle|Bernard Chazelle]] ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมนั้นมีความซับซ้อนมาก<br /> <br />
ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น <math>O (n)</math> ก็ได้ถูกค้นพบและตีพิมพ์โดย [[:en:Alexey V. Skvortsov|Alexey V. Skvortsov]] และ [[:en:Yuri L. Kostyuk|Yuri L. Kostyuk]] โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม <br/> <br />
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω (n log n)
 
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω <math>\Omega(n log n)</math>
 
== อ้างอิง ==
6,995

การแก้ไข