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

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

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

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

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

 อ้างอิง 

ทางเดียว
หมวดหมู่:ขั้นตอนวิธีเรขาคณิต