Menempatkan titik untuk memperkecil jarak dari titik terjauh

Lihat halaman ini. Ini menjelaskan beberapa metode untuk melakukan hal ini. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

_{Jika tautan di atas mati, inilah bagian relevan yang menjelaskan metode paling mudah:}

Algoritma O(n2)-waktu

1. Gambarlah sebuah lingkaran di pusat, c, sedemikian rupa sehingga titik-titik himpunan tertentu terletak di dalam lingkaran. Jelasnya, lingkaran ini bisa diperkecil (atau kita punya solusinya).
2. Buatlah lingkaran lebih kecil dengan mencari titik A yang terjauh dari pusat lingkaran, lalu menggambar lingkaran baru yang pusatnya sama dan melalui titik A. Kedua langkah ini menghasilkan lingkaran tertutup yang lebih kecil. Alasan mengapa lingkaran baru lebih kecil adalah karena lingkaran baru ini masih memuat semua titik dari himpunan tertentu, kecuali sekarang lingkaran tersebut melewati titik terjauh, x, dan bukan mengelilinginya.
3. Jika lingkaran melewati 2 titik atau lebih, lanjutkan ke langkah 4. Jika tidak, perkecil lingkaran dengan menggerakkan pusatnya ke arah titik A, hingga lingkaran tersebut menyentuh titik B lain dari himpunan.

4. Pada tahap ini, kita membuat lingkaran, C, yang melalui dua titik atau lebih pada suatu himpunan tertentu. Jika lingkaran mempunyai interval (interval bebas titik) busur yang lebih besar dari setengah keliling lingkaran yang tidak mempunyai titik, maka lingkaran dapat dibuat lebih kecil. Misalkan D dan E adalah titik-titik pada ujung interval bebas titik tersebut. Sambil menjaga D dan E pada batas lingkaran, kurangi diameter lingkaran hingga kita mendapatkan kasus (a) atau kasus (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.
     • JIKA tidak ada interval busur bebas titik yang keluar MAKA Kita selesai!
   • Else
     • Goto step 4.
     • Dalam hal ini, tiga titik harus terletak pada busur yang panjangnya kurang dari setengah keliling. Kita ulangi langkah 4 pada dua titik terluar dari tiga titik pada busur.

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

Anda perlu menggunakan Diagram Voronoi, mungkin diagram Voronoi Titik Terjauh, tempat bidang terbagi menjadi beberapa daerah dimana titik-titik pada daerah yang sama mempunyai titik terjauh yang sama

Perbarui

Anda perlu membuat diagram voronoi Titik Terjauh terlebih dahulu, yaitu O(nlogn) waktu, dan mencari pusat lingkaran terkecil di antara semua simpul (jika lingkaran dibatasi oleh tiga titik) dan semua sisinya (jika lingkaran ditentukan oleh dua titik). Total kompleksitas waktu dari pendekatan ini adalah O(nlogn)

Saya baru saja melihat halaman wiki Masalah lingkaran terkecil, sepertinya ada O(n ) algoritma waktu. Anda dapat memeriksanya jika Anda peduli dengan kecepatannya, jika tidak, sudahlah.