จุดศูนย์กลาง (เรขาคณิต)
ในสถิติและเรขาคณิตเชิงคำนวณแนวคิดของ จุดศูนย์กลางเป็นการขยายแนวคิดของค่ามัธยฐาน ไปยังข้อมูลใน ปริภูมิยูคลิดมิติสูงกว่าเมื่อกำหนดเซตของจุดใน ปริภูมิ 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 ]