กลับไปหน้าบทความ

อ่าน 4 นาที

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

การเปลี่ยนเส้นทางที่สามารถพิมพ์ได้/เปลี่ยนเส้นทางด้วยความเป็นไปได้

ในทางเรขาคณิตเซตK ⊂ R dถูกนิยามว่าเป็นเซตเว้าเชิงตั้งฉาก (orthogonally convex)ถ้าสำหรับทุกเส้นตรงLที่ขนานกับเวกเตอร์ฐานมาตรฐาน ตัวใดตัวหนึ่ง จุดตัดของKกับLจะเป็นเซตว่าง จุด...

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

ขอบเขตเชิงตั้งฉากนูนของเซตจุด

ในทางเรขาคณิตเซตKR dถูกนิยามว่าเป็นเซตเว้าเชิงตั้งฉาก (orthogonally convex)ถ้าสำหรับทุกเส้นตรงLที่ขนานกับเวกเตอร์ฐานมาตรฐาน ตัวใดตัวหนึ่ง จุดตัดของKกับLจะเป็นเซตว่าง จุด หรือส่วนของเส้น ตรงเพียงส่วนเดียว คำว่า "เชิงตั้งฉาก" หมายถึง ฐาน คาร์ทีเซียนและพิกัดที่สอดคล้องกันในปริภูมิยูคลิดซึ่งเวกเตอร์ฐานที่แตกต่างกันจะตั้งฉากกัน เช่นเดียวกับเส้นตรงที่สอดคล้องกัน แตกต่างจาก เซตเว้าทั่วไปเซตเว้าเชิงตั้งฉากไม่จำเป็นต้อง เป็นเซต ที่เชื่อมต่อกัน เสมอ ไป

ส่วนนูนเชิงตั้งฉากของเซตKR dคือจุดตัดของเซตย่อยนูนเชิงตั้งฉากที่เชื่อมต่อกันทั้งหมดของK

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

รูปทรงนูนเชิงตั้งฉากเรียกอีกอย่างว่ารูปทรงนูนเชิงเส้นตรงหรือในสองมิติเรียกว่ารูปทรงนูนx - y

ตัวอย่าง

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

คำจำกัดความทางเลือก

เซตของจุดหกจุดบนระนาบ ส่วนนูนเชิงตั้งฉากแบบคลาสสิก (Classical Ortho-convex Hull)คือเซตของจุดนั้นเอง
ขอบเขตนูนเชิงตั้งฉากสูงสุดของชุดจุดในรูปด้านบน เกิดจากการรวมกันของชุดจุดและพื้นที่สี
โครงร่างนูนเชิงตั้งฉากที่เชื่อมต่อกันของชุดจุดในรูปด้านบน เกิดจากชุดจุด พื้นที่สี และโซ่รูปหลายเหลี่ยมนูนเชิงตั้งฉากสองโซ่
ขอบเขตเชิงตั้งฉากนูนเชิงฟังก์ชัน ( Functional Ortho-convex Hull)ของเซตจุดในรูปด้านบน เกิดจากเซตจุด พื้นที่สี และส่วนของเส้นตรงทั้งสี่

ตรงกันข้ามกับความนูนแบบคลาสสิกที่มีนิยามของขอบนูนที่เทียบเท่ากันหลายแบบ นิยามของขอบนูนเชิงตั้งฉากที่สร้างขึ้นโดยการเปรียบเทียบกับนิยามของขอบนูนส่งผลให้ได้วัตถุทางเรขาคณิตที่แตกต่างกัน จนถึงปัจจุบัน นักวิจัยได้สำรวจนิยามของขอบนูนเชิงตั้งฉากของเซตไว้สี่แบบดังต่อไปนี้เคอาร์{\displaystyle K\subset \mathbb {R} ^{d}}:

  1. นิยามสูงสุด : นิยามที่อธิบายไว้ในบทนำของบทความนี้ ซึ่งอิงจากค่าสูงสุดของเซตจุด
  2. นิยามแบบดั้งเดิม : ส่วนนูนเชิงตั้งฉากของเค{\displaystyle K}คือจุดตัดของเซตย่อย นูนเชิงตั้งฉากทั้งหมด ของเค{\displaystyle K}; Ottmann, Soisalon-Soininen และไม้ (1984 )
  3. คำจำกัดความที่เชื่อมโยงกัน : ส่วนนูนเชิงตั้งฉากของเค{\displaystyle K}เป็นเซตย่อยที่เชื่อมต่อกันและนูนเชิงตั้งฉากที่เล็กที่สุดของเค{\displaystyle K}นิโคลและคณะ (1983 )
  4. นิยามเชิงฟังก์ชัน : ส่วนนูนเชิงตั้งฉากของเค{\displaystyle K}คือจุดตัดของเซตศูนย์ของฟังก์ชันนูนเชิงตั้งฉากที่ไม่เป็นลบทั้งหมดที่เป็น0{\displaystyle 0}บนเค{\displaystyle K}; มาตูเชคและเปลชาช (1998 )

ในภาพด้านขวา ภาพบนสุดแสดงชุดจุดหกจุดบนระนาบ ส่วนนูนเชิงตั้งฉากแบบคลาสสิกของชุดจุดนั้นก็คือชุดจุดนั้นเอง จากบนลงล่าง ภาพที่สองถึงภาพที่สี่แสดงส่วนนูนเชิงตั้งฉากสูงสุด ส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกัน และส่วนนูนเชิงตั้งฉากเชิงฟังก์ชันของชุดจุด ตามลำดับ จะเห็นได้ว่าส่วนนูนเชิงตั้งฉากเป็นรูปหลายเหลี่ยมที่มี "ขอบ" ที่เสื่อมสภาพบางส่วน กล่าวคือ โซ่รูปหลายเหลี่ยมสลับกันที่เป็นนูนเชิงตั้งฉากที่มีมุมภายใน90{\displaystyle 90^{\circ }}เชื่อมจุดยอดสุดขั้วเข้าด้วยกัน

เปลือกนูนเชิงตั้งฉากแบบคลาสสิก

ขอบเขตนูนเชิงตั้งฉากแบบคลาสสิกสามารถนิยามได้อย่างเทียบเท่าว่าเป็นเซตย่อยนูนเชิงตั้งฉากที่เล็กที่สุดของเซตหนึ่งเคอาร์2{\displaystyle K\subset \mathbb {R} ^{2}}โดยเปรียบเทียบกับนิยามของขอบนูนดังต่อไปนี้: ขอบนูนของเค{\displaystyle K}เป็นซูเปอร์เซตแบบนูนที่เล็กที่สุดของเค{\displaystyle K}ขอบเขตเชิงตั้งฉากแบบคลาสสิกอาจไม่เชื่อมต่อกัน หากเซตของจุดไม่มีจุดคู่ใดอยู่บนเส้นตรงที่ขนานกับเวกเตอร์ฐานมาตรฐานตัวใดตัวหนึ่ง ขอบเขตเชิงตั้งฉากแบบคลาสสิกของเซตของจุดนั้นจะเท่ากับเซตของจุดนั้นเอง

คุณสมบัติที่รู้จักกันดีของรูปทรงนูนนั้นได้มาจากทฤษฎีบทของคาราเธโอโดรี : จุดหนึ่งxอาร์{\displaystyle x\in \mathbb {R} ^{d}}อยู่ภายในขอบเขตนูนของเซตจุดเคอาร์{\displaystyle K\subset \mathbb {R} ^{d}}ก็ต่อเมื่อมันอยู่ในขอบเขตนูนของ+1{\displaystyle d+1}หรือคะแนนน้อยกว่าเค{\displaystyle K}คุณสมบัตินี้ยังใช้ได้กับรูปทรงนูนเชิงตั้งฉากแบบคลาสสิกด้วย

ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกัน

ตามนิยามแล้ว ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกันนั้นจะเชื่อมต่อกันเสมอ อย่างไรก็ตาม มันไม่ได้มีเพียงหนึ่งเดียว ตัวอย่างเช่น พิจารณาจุดสองจุดในระนาบที่ไม่วางอยู่บนเส้นแนวนอนหรือเส้นแนวตั้ง ขอบเขตนูนเชิงตั้งฉากที่เชื่อมต่อกันของจุดดังกล่าวคือโซ่รูปหลายเหลี่ยมสลับกันที่เป็นนูนเชิงตั้งฉาก โดยมีมุมภายในเท่ากับ 090{\displaystyle 90^{\circ }}การเชื่อมต่อจุดต่างๆ เข้าด้วยกัน โซ่รูปหลายเหลี่ยมดังกล่าวมีความยาวเท่ากัน ดังนั้นจึงมีรูปทรงนูนตั้งฉากที่เชื่อมต่อกันเป็นอนันต์สำหรับเซตของจุดเหล่านั้น

สำหรับเซตของจุดในระนาบนั้น ส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกันสามารถหาได้ง่ายจากส่วนนูนเชิงตั้งฉากสูงสุด หากส่วนนูนเชิงตั้งฉากสูงสุดของเซตของจุดเคอาร์2{\displaystyle K\subset \mathbb {R} ^{2}}ถ้าเชื่อมต่อกันแล้ว มันจะเท่ากับส่วนนูนเชิงตั้งฉากที่เชื่อมต่อกันของเค{\displaystyle K}หากไม่ใช่เช่นนั้น ก็จะมีรูปทรงนูนตั้งฉากที่เชื่อมต่อกันเป็นจำนวนอนันต์สำหรับเค{\displaystyle K}และแต่ละส่วนสามารถได้มาจากการเชื่อมต่อส่วนประกอบที่เชื่อมต่อกันของส่วนนูนเชิงตั้งฉากสูงสุดของเค{\displaystyle K}โดยมีโซ่รูปหลายเหลี่ยมสลับกันที่มีลักษณะนูนตั้งฉากกันและมีมุมภายใน90{\displaystyle 90^{\circ }}.

ขอบเขตนูนเชิงตั้งฉากเชิงฟังก์ชัน

ขอบเขตเชิงฟังก์ชันตั้งฉากนูนไม่ได้ถูกนิยามโดยใช้คุณสมบัติของเซต แต่ใช้คุณสมบัติของฟังก์ชันเกี่ยวกับเซต กล่าวคือ มันจำกัดแนวคิดของฟังก์ชันนูนดังต่อไปนี้ ฟังก์ชันเอฟ:อาร์อาร์{\displaystyle f:\mathbb {R} ^{d}\rightarrow \mathbb {R} }เรียกว่าฟังก์ชันนูนเชิงตั้งฉาก (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)อธิบายผลลัพธ์อื่นๆ อีกหลายประการเกี่ยวกับความนูนเชิงตั้งฉากและการมองเห็น เชิง ตั้ง ฉาก

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Orthogonal_convex_hull&oldid=1278906689 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ เปลือกนูนตั้งฉาก

ในทางเรขาคณิตเซตK ⊂ R dถูกนิยามว่าเป็นเซตเว้าเชิงตั้งฉาก (orthogonally convex)ถ้าสำหรับทุกเส้นตรงLที่ขนานกับเวกเตอร์ฐานมาตรฐาน ตัวใดตัวหนึ่ง จุดตัดของKกับLจะเป็นเซตว่าง จุด...

ตัวอย่าง

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

คำจำกัดความทางเลือก

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

เปลือกนูนเชิงตั้งฉากแบบคลาสสิก

ขอบเขตนูนเชิงตั้งฉากแบบคลาสสิกสามารถนิยามได้อย่างเทียบเท่าว่าเป็นเซตย่อยนูนเชิงตั้งฉากที่เล็กที่สุดของเซตหนึ่ง เค ⊂ อาร์ 2 {\displaystyle K\subset \mathbb {R} ^{2}} โดยเปรียบเทียบกับนิยามของขอบนูนดังต่อไปนี้: ขอบนูนของ เค {\displaystyle K}...