การวางจุดเพื่อลดระยะห่างจากจุดที่ไกลที่สุด

ตรวจสอบหน้านี้ โดยจะอธิบายวิธีการต่างๆ มากมายในการทำเช่นนี้ http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

_{ในกรณีที่ลิงก์ด้านบนเสีย นี่คือส่วนที่เกี่ยวข้องซึ่งอธิบายวิธีการที่ตรงไปตรงมาที่สุด:}

อัลกอริธึมเวลา O(n2)

1. วาดวงกลมตรงกลาง c โดยให้จุดที่กำหนดอยู่ภายในวงกลม เห็นได้ชัดว่าวงกลมนี้สามารถย่อให้เล็กลงได้ (หรืออย่างอื่นเรามีวิธีแก้ปัญหา)
2. ทำให้วงกลมเล็กลงโดยหาจุด A ที่ไกลที่สุดจากจุดศูนย์กลางของวงกลม แล้ววาดวงกลมใหม่โดยมีจุดศูนย์กลางเดียวกันแล้วผ่านจุด A ขั้นตอนทั้งสองนี้จะทำให้เกิดวงกลมล้อมรอบที่เล็กลง เหตุผลที่วงกลมใหม่มีขนาดเล็กลงก็เนื่องมาจากวงกลมใหม่นี้ยังคงมีจุดทั้งหมดของเซตที่กำหนด ยกเว้นตอนนี้มันจะผ่านจุดที่ไกลที่สุด x แทนที่จะล้อมรอบไว้
3. หากวงกลมผ่าน 2 จุดขึ้นไป ให้ดำเนินการขั้นตอนที่ 4 หรือทำให้วงกลมเล็กลงโดยเลื่อนจุดศูนย์กลางไปทางจุด A จนกระทั่งวงกลมสัมผัสกับจุด B อีกจุดหนึ่งจากเซต

4. ในขั้นนี้ เราจะสร้างวงกลม C ซึ่งผ่านจุดสองจุดขึ้นไปของเซตที่กำหนด ถ้าวงกลมมีช่วงเวลา (ช่วงไร้จุด) ของส่วนโค้งที่มากกว่าครึ่งหนึ่งของเส้นรอบวงของวงกลมที่ไม่มีจุดอยู่ วงกลมก็สามารถทำให้เล็กลงได้ ให้ D และ E เป็นจุดสิ้นสุดของช่วงไร้จุดนี้ ขณะที่ให้ D และ E อยู่บนขอบเขตของวงกลม ให้ลดเส้นผ่านศูนย์กลางของวงกลมลงจนกว่าเราจะได้กรณี (a) หรือกรณี (b)

   • Case (a) The diameter is the distance DE.
     • We are done!
   • Case (b) The circle C touches another point from the set, F.
     • Check whether there exits point-free arc intervals of length more than half the circumference of C.
     • หากไม่มีช่วงส่วนโค้งที่ไม่มีจุดดังกล่าวออก เราก็เสร็จแล้ว!
   • Else
     • Goto step 4.
     • ในกรณีนี้ จุดสามจุดต้องอยู่บนส่วนโค้งน้อยกว่าครึ่งหนึ่งของความยาวเส้นรอบวง เราทำซ้ำขั้นตอนที่ 4 ที่ด้านนอกสองจุดจากสามจุดบนส่วนโค้ง

Another page here, with a sample applet: http://www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

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

อัปเดต

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

ฉันเพิ่งเห็นหน้าวิกิ ปัญหาวงกลมที่เล็กที่สุด ดูเหมือนว่าจะมี O(n ) อัลกอริธึมเวลา คุณสามารถตรวจสอบได้ว่าคุณสนใจเรื่องความเร็วหรือไม่ ไม่อย่างนั้นก็ไม่เป็นไร