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

อ่าน 2 นาที

จุดศูนย์กลาง (เรขาคณิต)

วิธี/สถิติที่แข็งแกร่ง

ในสถิติและเรขาคณิตเชิงคำนวณแนวคิดของ จุดศูนย์กลางเป็นการขยายแนวคิดของค่ามัธยฐาน ไปยังข้อมูลใน ปริภูมิยูคลิดมิติสูงกว่าเมื่อกำหนดเซตของจุดใน ปริภูมิ dมิติ...

จุดศูนย์กลาง (เรขาคณิต)

ในสถิติและเรขาคณิตเชิงคำนวณแนวคิดของ จุดศูนย์กลางเป็นการขยายแนวคิดของค่ามัธยฐาน ไปยังข้อมูลใน ปริภูมิยูคลิดมิติสูงกว่าเมื่อกำหนดเซตของจุดใน ปริภูมิ dมิติ จุดศูนย์กลางของเซตคือจุดที่ระนาบใดๆ ที่ผ่านจุดนั้นจะแบ่งเซตของจุดออกเป็นสองเซตย่อยที่มีขนาดใกล้เคียงกัน โดยส่วนที่เล็กกว่าจะต้องมีจุดอย่างน้อย 1/( d  +  1) เช่นเดียวกับค่ามัธยฐาน จุดศูนย์กลางไม่จำเป็นต้องเป็นจุดข้อมูลใดๆ เซตของจุดที่ไม่ว่างเปล่าทุกเซต (โดยไม่มีจุดซ้ำ) จะมีจุดศูนย์กลางอย่างน้อยหนึ่งจุด

แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดคือความลึกของทูคีย์ (จำนวนจุดตัวอย่างขั้นต่ำบนด้านใดด้านหนึ่งของระนาบที่ผ่านจุดนั้น) และค่ามัธยฐานของทูคีย์ของกลุ่มจุด (จุดที่ทำให้ความลึกของทูคีย์สูงสุด) จุดศูนย์กลางคือจุดที่มีความลึกอย่างน้อยn /( d  +  1) และค่ามัธยฐานของทูคีย์ต้องเป็นจุดศูนย์กลาง แต่ไม่ใช่ว่าทุกจุดศูนย์กลางจะเป็นค่ามัธยฐานของทูคีย์ ทั้งสองคำนี้ตั้งชื่อตามจอห์น ทูคีย์

สำหรับการขยายความค่ามัธยฐานไปสู่มิติที่สูงขึ้น โปรดดูที่ ค่ามัธยฐานเชิงเรขาคณิต

การดำรงอยู่

สามารถพิสูจน์การมีอยู่ของจุดศูนย์กลางอย่างง่ายได้โดยใช้ทฤษฎีบทของเฮลลีสมมติว่ามี จุด nจุด และพิจารณาตระกูลของครึ่งพื้นที่ ปิด ที่บรรจุจุดมากกว่าdn /( d  +  1) จุด มีจุดน้อยกว่าn /( d  +  1) จุดที่ถูกยกเว้นจากครึ่งพื้นที่ใดๆ เหล่านี้ ดังนั้นส่วนตัดกันของเซตย่อยใดๆ ของ ครึ่งพื้นที่ d  +  1 จะต้องไม่ว่างเปล่า จากทฤษฎีบทของเฮลลี จึงสรุปได้ว่าส่วนตัดกันของครึ่งพื้นที่ทั้งหมดเหล่านี้ก็ต้องไม่ว่างเปล่าเช่นกัน จุดใดๆ ในส่วนตัดกันนี้จึงจำเป็นต้องเป็นจุดศูนย์กลาง

อัลกอริทึม

สำหรับจุดในระนาบยุคลิดจุดศูนย์กลางสามารถสร้างได้ในเวลาเชิงเส้น [ 1 ] ในมิติใดๆdค่ามัธยฐานของ Tukey (และด้วยเหตุนี้จุดศูนย์กลางด้วย) สามารถสร้างได้ในเวลา O( n d 1    + n log n ) [ 2 ]   

อัลกอริทึมแบบสุ่มที่แทนที่ชุดจุดd  +  2 จุดซ้ำๆ ด้วยจุด Radonสามารถใช้คำนวณค่าประมาณของจุดศูนย์กลางของชุดจุดใดๆ ก็ได้ ในแง่ที่ว่าความลึกของ Tukey นั้นเป็นเชิงเส้นตามขนาดของชุดตัวอย่าง ในช่วงเวลาที่เป็นพหุนามตามมิติ[ 3 ] [ 4 ]

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

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ จุดศูนย์กลาง (เรขาคณิต)

ในสถิติและเรขาคณิตเชิงคำนวณแนวคิดของ จุดศูนย์กลางเป็นการขยายแนวคิดของค่ามัธยฐาน ไปยังข้อมูลใน ปริภูมิยูคลิดมิติสูงกว่าเมื่อกำหนดเซตของจุดใน ปริภูมิ dมิติ...

แนวคิดที่เกี่ยวข้อง

แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดคือ ความลึก ของทูคีย์ (จำนวนจุดตัวอย่างขั้นต่ำบนด้านใดด้านหนึ่งของระนาบที่ผ่านจุดนั้น) และ ค่ามัธยฐานของทูคีย์ ของกลุ่มจุด (จุดที่ทำให้ความลึกของทูคีย์สูงสุด) จุดศูนย์กลางคือจุดที่มีความลึกอย่างน้อย n /( d + 1)...

การดำรงอยู่

สามารถพิสูจน์การมีอยู่ของจุดศูนย์กลางอย่างง่ายได้โดยใช้ ทฤษฎีบทของเฮลลี สมมติว่ามี จุด n จุด และพิจารณาตระกูลของ ครึ่งพื้นที่ ปิด ที่บรรจุจุดมากกว่า dn /( d + 1) จุด มีจุดน้อยกว่า n /( d + 1) จุดที่ถูกยกเว้นจากครึ่งพื้นที่ใดๆ เหล่านี้...

อัลกอริทึม

สำหรับจุดใน ระนาบยุคลิด จุดศูนย์กลางสามารถสร้างได้ใน เวลาเชิงเส้น [ 1 ] ใน มิติใดๆ d ค่ามัธยฐานของ Tukey (และด้วยเหตุนี้จุดศูนย์กลางด้วย) สามารถสร้างได้ในเวลา O( n d − 1 + n log n ) [ 2 ]