รูปหลายเหลี่ยมทางเดียว

รูปหลายเหลี่ยมทางเดียว (อังกฤษ: monotone polygon) คือรูปหลายเหลี่ยม P บนระนาบ ซึ่งเมื่อกำหนดเส้นตรง L ขึ้นมาเส้นหนึ่ง เส้นตรงทุกเส้นที่ตั้งฉากกับ L จะลากตัดผ่านเส้นขอบของรูปหลายเหลี่ยม P อย่างมากที่สุดเพียงสองครั้ง สำหรับจุดประสงค์ในทางปฏิบัติหลายอย่าง นิยามนี้อาจขยายออกไป ให้สามารถยอมรับกรณีที่เส้นขอบของ P บางเส้นตั้งฉากกับ L

สมบัติ

เส้นสีเขียวแสดงส่วนที่ตัดหนึ่งครั้ง เส้นสีน้ำเงินตัดสองครั้ง เส้นสีแดงตัดสามครั้งหรือมากกว่า เฉพาะสองรูปบนจึงเป็นรูปหลายเหลี่ยมทางเดียว ในขณะที่อีกสองรูปล่างไม่ใช่

สมมติให้เส้นตรง L ทับกันสนิทกับแกน x จุดยอดที่อยู่ทางซ้ายสุดหรือขวาสุดของรูปหลายเหลี่ยมทางเดียว จะสามารถแบ่งเส้นขอบของรูปออกเป็น (polygonal chain) สองรูป ซึ่งจุดยอดบนลูกโซ่หลายเหลี่ยมจะเรียงตัวในลำดับธรรมชาติ นั่นคือพิกัด x ของจุดยอดจะมีค่าเพิ่มหรือลดไปในทางเดียว ไม่เพิ่มลดสลับไปมา สมบัตินี้จึงอาจใช้เป็นนิยามของรูปหลายเหลี่ยมทางเดียวก็ได้

รูปหลายเหลี่ยมนูนทุกรูปเป็นรูปหลายเหลี่ยมทางเดียว ซึ่งสามารถพิสูจน์ได้จากเส้นตรงใดๆ ที่ตัดผ่าน

การค้นหาจุดตัดของเส้นตรงกับรูปหลายเหลี่ยมทางเดียว เพื่อที่จะหาว่าจุดยอดใดอยู่ทางซ้ายสุดหรือขวาสุด อาจต้องใช้เวลาคำนวณเป็นเวลาลอการิทึม หลังจากประมวลผลก่อนเป็นเวลาเชิงเส้นไปแล้ว รูปหลายเหลี่ยมทางเดียวอาจแบ่งออกเป็นรูปสามเหลี่ยมได้โดยง่ายในเวลาเชิงเส้น

อ้างอิง

1. and (1985). Computational Geometry - An Introduction. . 1st edition: ; 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989: .
2. ; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", , 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301