เปลือกนูนตั้งฉาก

ในทางเรขาคณิตเซตK ⊂ R dถูกนิยามว่าเป็นเซตเว้าเชิงตั้งฉาก (orthogonally convex)ถ้าสำหรับทุกเส้นตรงLที่ขนานกับเวกเตอร์ฐานมาตรฐาน ตัวใดตัวหนึ่ง จุดตัดของKกับLจะเป็นเซตว่าง จุด หรือส่วนของเส้น ตรงเพียงส่วนเดียว คำว่า "เชิงตั้งฉาก" หมายถึง ฐาน คาร์ทีเซียนและพิกัดที่สอดคล้องกันในปริภูมิยูคลิดซึ่งเวกเตอร์ฐานที่แตกต่างกันจะตั้งฉากกัน เช่นเดียวกับเส้นตรงที่สอดคล้องกัน แตกต่างจาก เซตเว้าทั่วไปเซตเว้าเชิงตั้งฉากไม่จำเป็นต้อง เป็นเซต ที่เชื่อมต่อกัน เสมอ ไป
ส่วนนูนเชิงตั้งฉากของเซตK ⊂ R dคือจุดตัดของเซตย่อยนูนเชิงตั้งฉากที่เชื่อมต่อกันทั้งหมดของK
คำจำกัดความเหล่านี้สร้างขึ้นโดยการเปรียบเทียบกับทฤษฎีความนูนแบบคลาสสิก ซึ่งKเป็น เซต แบบนูนก็ต่อเมื่อ สำหรับทุกเส้นตรงLจุดตัดของKกับLเป็นเซตว่าง จุด หรือส่วนของเส้นตรงเพียงเส้นเดียว ความนูนเชิงตั้งฉากจำกัดเส้นตรงที่ต้องมีคุณสมบัตินี้ ดังนั้นเซตแบบนูนทุกเซตจึงเป็นเซตแบบนูนเชิงตั้งฉาก แต่ในทางกลับกันไม่ใช่ ด้วยเหตุผลเดียวกันนี้ เปลือกนูนเชิงตั้งฉากเองก็เป็นเซตย่อยของเปลือกนูนของเซตจุดเดียวกัน จุดpอยู่ในเปลือกนูนเชิงตั้งฉากของK ก็ต่อเมื่อแต่ละออร์ แธนต์ปิดที่วางตัวตามแกน โดยมีpเป็นจุดยอด มีจุดตัดกับK ที่ไม่ว่าง เปล่า
รูปทรงนูนเชิงตั้งฉากเรียกอีกอย่างว่ารูปทรงนูนเชิงเส้นตรงหรือในสองมิติเรียกว่ารูปทรงนูนx - y
ตัวอย่าง
ภาพแสดงชุดจุด 16 จุดบนระนาบและรูปทรงนูนเชิงตั้งฉากของจุดเหล่านี้ ดังที่เห็นได้ในภาพ รูปทรงนูนเชิงตั้งฉากเป็นรูปหลายเหลี่ยมที่มีขอบบางส่วนเชื่อมต่อจุดยอดสุดขั้วในแต่ละทิศทางพิกัด สำหรับชุดจุดแบบไม่ต่อเนื่องเช่นนี้ ขอบทั้งหมดของรูปทรงนูนเชิงตั้งฉากจะเป็นเส้นแนวนอนหรือแนวตั้ง ในตัวอย่างนี้ รูปทรงนูนเชิงตั้งฉากเป็นเส้นเชื่อมต่อ
คำจำกัดความทางเลือก




ตรงกันข้ามกับความนูนแบบคลาสสิกที่มีนิยามของขอบนูนที่เทียบเท่ากันหลายแบบ นิยามของขอบนูนเชิงตั้งฉากที่สร้างขึ้นโดยการเปรียบเทียบกับนิยามของขอบนูนส่งผลให้ได้วัตถุทางเรขาคณิตที่แตกต่างกัน จนถึงปัจจุบัน นักวิจัยได้สำรวจนิยามของขอบนูนเชิงตั้งฉากของเซตไว้สี่แบบดังต่อไปนี้:
- นิยามสูงสุด : นิยามที่อธิบายไว้ในบทนำของบทความนี้ ซึ่งอิงจากค่าสูงสุดของเซตจุด
- นิยามแบบดั้งเดิม : ส่วนนูนเชิงตั้งฉากของคือจุดตัดของเซตย่อย นูนเชิงตั้งฉากทั้งหมด ของ; Ottmann, Soisalon-Soininen และไม้ (1984 )
- คำจำกัดความที่เชื่อมโยงกัน : ส่วนนูนเชิงตั้งฉากของเป็นเซตย่อยที่เชื่อมต่อกันและนูนเชิงตั้งฉากที่เล็กที่สุดของนิโคลและคณะ (1983 )
- นิยามเชิงฟังก์ชัน : ส่วนนูนเชิงตั้งฉากของคือจุดตัดของเซตศูนย์ของฟังก์ชันนูนเชิงตั้งฉากที่ไม่เป็นลบทั้งหมดที่เป็นบน; มาตูเชคและเปลชาช (1998 )
ในภาพด้านขวา ภาพบนสุดแสดงชุดจุดหกจุดบนระนาบ ส่วนนูนเชิงตั้งฉากแบบคลาสสิกของชุดจุดนั้นก็คือชุดจุดนั้นเอง จากบนลงล่าง ภาพที่สองถึงภาพที่สี่แสดงส่วนนูนเชิงตั้งฉากสูงสุด ส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกัน และส่วนนูนเชิงตั้งฉากเชิงฟังก์ชันของชุดจุด ตามลำดับ จะเห็นได้ว่าส่วนนูนเชิงตั้งฉากเป็นรูปหลายเหลี่ยมที่มี "ขอบ" ที่เสื่อมสภาพบางส่วน กล่าวคือ โซ่รูปหลายเหลี่ยมสลับกันที่เป็นนูนเชิงตั้งฉากที่มีมุมภายในเชื่อมจุดยอดสุดขั้วเข้าด้วยกัน
เปลือกนูนเชิงตั้งฉากแบบคลาสสิก
ขอบเขตนูนเชิงตั้งฉากแบบคลาสสิกสามารถนิยามได้อย่างเทียบเท่าว่าเป็นเซตย่อยนูนเชิงตั้งฉากที่เล็กที่สุดของเซตหนึ่งโดยเปรียบเทียบกับนิยามของขอบนูนดังต่อไปนี้: ขอบนูนของเป็นซูเปอร์เซตแบบนูนที่เล็กที่สุดของขอบเขตเชิงตั้งฉากแบบคลาสสิกอาจไม่เชื่อมต่อกัน หากเซตของจุดไม่มีจุดคู่ใดอยู่บนเส้นตรงที่ขนานกับเวกเตอร์ฐานมาตรฐานตัวใดตัวหนึ่ง ขอบเขตเชิงตั้งฉากแบบคลาสสิกของเซตของจุดนั้นจะเท่ากับเซตของจุดนั้นเอง
คุณสมบัติที่รู้จักกันดีของรูปทรงนูนนั้นได้มาจากทฤษฎีบทของคาราเธโอโดรี : จุดหนึ่งอยู่ภายในขอบเขตนูนของเซตจุดก็ต่อเมื่อมันอยู่ในขอบเขตนูนของหรือคะแนนน้อยกว่าคุณสมบัตินี้ยังใช้ได้กับรูปทรงนูนเชิงตั้งฉากแบบคลาสสิกด้วย
ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกัน
ตามนิยามแล้ว ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกันนั้นจะเชื่อมต่อกันเสมอ อย่างไรก็ตาม มันไม่ได้มีเพียงหนึ่งเดียว ตัวอย่างเช่น พิจารณาจุดสองจุดในระนาบที่ไม่วางอยู่บนเส้นแนวนอนหรือเส้นแนวตั้ง ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกันของจุดดังกล่าวคือโซ่รูปหลายเหลี่ยมสลับกันที่เป็นนูนเชิงตั้งฉาก โดยมีมุมภายในเท่ากับ 0การเชื่อมต่อจุดต่างๆ เข้าด้วยกัน โซ่รูปหลายเหลี่ยมดังกล่าวมีความยาวเท่ากัน ดังนั้นจึงมีรูปทรงนูนตั้งฉากที่เชื่อมต่อกันเป็นอนันต์สำหรับเซตของจุดเหล่านั้น
สำหรับเซตของจุดในระนาบนั้น ส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกันสามารถหาได้ง่ายจากส่วนนูนเชิงตั้งฉากสูงสุด หากส่วนนูนเชิงตั้งฉากสูงสุดของเซตของจุดถ้าเชื่อมต่อกันแล้ว มันจะเท่ากับส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกันของหากไม่ใช่เช่นนั้น ก็จะมีรูปทรงนูนตั้งฉากที่เชื่อมต่อกันเป็นจำนวนอนันต์สำหรับและแต่ละส่วนสามารถได้มาจากการเชื่อมต่อส่วนประกอบที่เชื่อมต่อกันของส่วนนูนเชิงตั้งฉากสูงสุดของโดยมีโซ่รูปหลายเหลี่ยมสลับกันที่มีลักษณะนูนตั้งฉากกันและมีมุมภายใน.
ขอบเขตนูนเชิงตั้งฉากเชิงฟังก์ชัน
ขอบเขตเชิงฟังก์ชันตั้งฉากนูนไม่ได้ถูกนิยามโดยใช้คุณสมบัติของเซต แต่ใช้คุณสมบัติของฟังก์ชันเกี่ยวกับเซต กล่าวคือ มันจำกัดแนวคิดของฟังก์ชันนูนดังต่อไปนี้ ฟังก์ชันเรียกว่าฟังก์ชันนูนเชิงตั้งฉาก (orthogonally convex) ถ้าการจำกัดฟังก์ชันนั้นบนเส้นตรงแต่ละเส้นที่ขนานกับเวกเตอร์ฐานมาตรฐานที่ไม่ใช่ศูนย์ เป็นฟังก์ชันนูน
อัลกอริทึม
นักวิจัยหลายท่านได้ศึกษาอัลกอริทึมสำหรับการสร้างขอบเขตนูนเชิงตั้งฉาก ได้แก่Montuno & Fournier (1982) ; Nicholl et al. (1983) ; Ottmann, Soisalon-Soininen & Wood (1984) ; Karlsson & Overmars (1988)จากผลการวิจัยของนักวิจัยเหล่านี้ ขอบเขตนูนเชิงตั้งฉากของ จุด nจุดในระนาบสามารถสร้างได้ในเวลาO ( n log n )หรืออาจเร็วกว่านั้นหากใช้โครงสร้างข้อมูลการค้นหาจำนวนเต็มสำหรับจุดที่มีพิกัดเป็นจำนวนเต็ม
แนวคิดที่เกี่ยวข้อง
เป็นเรื่องปกติที่จะขยายแนวคิดความนูนเชิงตั้งฉากไปสู่ความนูนเชิงทิศทางที่จำกัดโดยที่เซตK จะถูกนิยามว่าเป็นเซตนูนก็ต่อเมื่อเส้นตรงทั้งหมดที่มี ความชันหนึ่งในเซตจำกัด จะต้องตัดกับ Kในเซตย่อยที่เชื่อมต่อกัน ดูตัวอย่างเช่นRawlins (1987) , Rawlins and Wood ( 1987 , 1988 )หรือFink and Wood ( 1996 , 1998 )
นอกจากนี้ช่วงแคบ (tight span) ของ ปริภูมิเมตริกจำกัดยังมีความสัมพันธ์อย่างใกล้ชิดกับส่วนนูนเชิงตั้งฉาก (orthogonal convex hull) หากเซตจุดจำกัดในระนาบมีส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกัน ส่วนนูนนั้นจะเป็นช่วงแคบสำหรับระยะทางแมนฮัตตัน บนเซตจุดนั้น อย่างไรก็ตาม ส่วนนูนเชิงตั้งฉากและช่วงแคบจะแตกต่างกันสำหรับเซตจุดที่มีส่วนนูนเชิงตั้งฉากที่ไม่เชื่อมต่อกัน หรือใน ปริภูมิL pที่มีมิติสูงกว่า
O'Rourke (1993)อธิบายผลลัพธ์อื่นๆ อีกหลายประการเกี่ยวกับความนูนเชิงตั้งฉากและการมองเห็น เชิง ตั้ง ฉาก