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

'''โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยม''' ([[อังกฤษ]]:Polygon Triangulation) คือการแบ่ง[[รูปหลายเหลี่ยม]]เป็นเซ็ทของ[[สามเหลี่ยม]]ที่มากกว่า 1 รูป ซึ่งไม่ทับกันเลย สำหรับอัลกอริทึมขั้นตอนวิธีที่ใช้ในการแบ่งนั้นสำหรับรูปหลายเหลี่ยมที่มีและไม่มีรูภายในจะแตกต่างกัน

==== อัลกอริทึมขั้นตอนวิธี ====

กำหนดให้ S คือเซ็ทของเส้นขอบของรูปหลายเหลี่ยมที่ไม่ใช่เส้นแนวนอนและไม่ตัดกัน อัลกอริทึมขั้นตอนวิธีแบบสุ่ม ({{lang-en|Randomised Algorithm}}) จะถูกใช้เพื่อสร้างสี่เหลี่ยมคางหมูจากเส้นตรงใน S ซึ่งจะทำโดยจะดึงเส้นตรงใน S ออกมาทีละเส้นแบบสุ่มเพื่อสร้างเป็นสี่เหลี่ยมคางหมู วิธีนี้จะแบ่งรูปหลายเหลี่ยมเป็นสี่เหลี่ยมคางหมูจำนวนหนึ่งตัวสี่เหลี่ยมคางหมูนี้สามารถลดรุปเป็นสามเหลี่ยมได้ถ้ามีขอบด้านใดด้านหนึ่งมีความยาวด้านนอนเป็นศูนย์ สำหรับเงื่อนไขที่ว่าเส้นในเซ็ทจะต้องไม่เป็นเส้นนอนนั้นมีขึ้นเพื่อจำกัดจำนวนที่ต้องทำให้ลดน้อยลง แต่ก็ไม่ได้ส่งผลอะไรต่อผลลัพธ์ที่จะได้ ซึ่งจากที่ [[:en:Siedal|Siedal]] ได้พิสูจน์ไว้เราสรุปได้ว่าขั้นตอนนี้ใช้เวลาในการทำงานเป็น <math>O (nlog n)</math>

รูปหลายเหลี่ยมทางเดียวสามารถแยกเป็นสามเหลี่ยมได้โดยใช้อัลกอริทึมขั้นตอนวิธีเชิงละโมบ โดยให้ตัดมุมเว้าไปเรื่อยๆ ซึ่งในส่วนนี้จะใช้เวลาเป็น <math>O(n)</math>

โครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นเป็นปัญหาที่มีการคิดกันมานานแล้วว่าจะสามารถทำให้ได้ไวกว่า <math>O(n log n)</math> ได้หรือไม่ ในปี 1990 นั้น [[:en:David G. Kirkpatrick|David G. Kirkpatrick]],[[:en:David G. Kirkpatrick|David G. Kirkpatrick]], [[: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)</math> เลย

นอกจากวิธีการข้างต้นแล้ว [[:en:Bernard Chazelle|Bernard Chazelle]] ยังได้แสดงให้เห็นว่าโครงข่ายสามเหลี่ยมของรูปหลายเหลี่ยมนั้นสามารถหาได้ด้วยเวลาเชิงเส้น แต่อัลกอริทึมขั้นตอนวิธีนั้นมีความซับซ้อนมาก

ต่อมาในปี 1998 อัลกอริทึมขั้นตอนวิธีที่ใช้เวลาเฉลี่ยเป็น <math>O(n)</math> ก็ได้ถูกค้นพบและตีพิมพ์โดย [[:en:Alexey V. Skvortsov|Alexey V. Skvortsov]] และ [[:en:Yuri L. Kostyuk|Yuri L. Kostyuk]] โดยอัลกอริทึมขั้นตอนวิธีนี้จะใช้หลักการของกำหนดการพลวัตในการจำรูปสามเหลี่ยม

ส่วนความซับซ้อนทางด้านเวลาของอัลกอริทึมขั้นตอนวิธีในการหาโครงข่ายสามเหลี่ยมของรูปสามเหลี่ยมที่มีรูภายในนั้นจะใช้เวลาเป็น <math>\Omega(n log n)</math>