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

ไม่มีคำอธิบายอย่างย่อ
:::/* The angle is reflex or cardinality of L is 1 */<br />
:::Add p to L<br />
===ความซับซ้อนในการคำนวณ===
โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า 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 />
นอกจากวิธีการข้างต้นแล้ว [[Bernard Chazelle]] ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมนั้นมีความซับซ้อนมาก<br /> <br />
ต่อมาในปี 1998 อัลกอริทึมที่ใช้เวลาเฉลี่ยเป็น O(n) ก็ได้ถูกค้นพบและตีพิมพ์โดย [[Alexey V. Skvortsov]] และ [[Yuri L. Kostyuk]] โดยอัลกอริทึมนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม <br/> <br />
ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น Ω(n log n)
23

การแก้ไข