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

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

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

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