Temukan titik pusat dalam set titik ruang metrik, dalam waktu kurang dari

Saya memiliki satu set titik yang didefinisikan dalam ruang metrik - jadi saya dapat mengukur 'jarak' antara titik tetapi tidak ada yang lain. Saya ingin menemukan titik paling sentral dalam himpunan ini, yang saya definisikan sebagai titik dengan jumlah minimum jarak ke semua titik lainnya. Perhitungan metrik lambat, jadi harus dihindari sedapat mungkin. $n$

Cara yang jelas untuk menemukan titik ini menggunakan perhitungan jarak metrik, karena hanya (a) menghitung untuk setiap titik jumlah jarak ke semua titik lainnya dan kemudian (b) mengambil titik minimum. $n^2$

Apakah ada cara untuk melakukan ini dalam perbandingan jarak kurang dari ? (Mungkin memanfaatkan ketimpangan segitiga dalam beberapa cara, yang seharusnya berlaku dengan metrik saya.) $O(n^2)$

Perkiraan yang baik mungkin cukup jika metode yang tepat tidak ada.

complexity-theory computational-geometry lower-bounds search-problem Logistik Pintu Terbuka
sumber

Tanpa ketimpangan segitiga (atau cara lain untuk mendapatkan informasi tentang tepi yang tidak terukur),

adalah satu-satunya solusi; ini bisa dilihat dengan argumen antagonis.

O (n^{2})

$O(n^2)$

Kittsil

Asumsikan ketidaksamaan segitiga tersedia - seharusnya untuk metrik saya.

Logistik Pintu Terbuka

Ini pada dasarnya menghitung radio grafik dengan persamaan segitiga.

Kaveh

@ Kaveh Saya kira maksud Anda jari-jari ... kecuali grafik memiliki tepi yang rusak. Saya memastikan karena ada terlalu banyak kosakata yang saya tidak tahu. --- Tapi itu kemudian grafik lengkap, dan ukuran input hanya jumlah simpul.

babou

@OpenDoorLogistics Jika tidak memiliki ketimpangan segitiga, itu bukan ruang metrik, oleh deifinition. Tolong jelaskan pertanyaannya: jika Anda tahu ini adalah ruang metrik, maka Anda tahu itu memiliki ketimpangan segitiga; jika Anda tidak tahu itu memiliki ketimpangan segitiga, Anda tidak dapat mengklaim itu adalah ruang metrik.

David Richerby

Jawaban:

Tidak. Anda tidak dapat melakukan lebih baik dari dalam kasus terburuk. $\Theta(n^2)$

Pertimbangkan pengaturan titik di mana setiap pasangan titik berada pada jarak dari satu sama lain. (Ini adalah konfigurasi yang mungkin.) Maka Anda tidak dapat melakukan lebih baik daripada memeriksa setiap sisi. Khususnya, jika ada sisi yang belum Anda periksa, maka musuh dapat memilih panjang sisi itu menjadi , , atau ; semua pilihan itu konsisten dengan semua pengamatan lain yang telah Anda buat dan dengan persyaratan metrik (misalnya, dengan ketimpangan segitiga), sehingga ketiganya mungkin; tetapi mereka membutuhkan keluaran yang berbeda. Jadi, jika algoritme Anda tidak memeriksa tepi itu dan kemudian mengeluarkan sesuatu, musuh selalu dapat memilih panjang untuk tepi yang tidak diperiksa yang akan membuat output algoritme Anda salah. $1$ $0.9$ $1.0$ $1.1$

Namun, jika Anda tahu bahwa semua titik hidup dalam (meskipun Anda tidak diberi koordinatnya), maka masalahnya dapat diselesaikan dengan mengukur jarak , dengan asumsi tidak ada degenerasi (tanpa subset dari poin adalah co-planar). $\mathbb{R}^d$ $O((d+1)n)$ $d+1$

Secara khusus, pilih poin secara acak. Ini akan menjadi titik jangkar. Mengingat jarak berpasangan mereka, Anda dapat menghitung koordinat untuk mereka yang konsisten dengan jarak berpasangan mereka. Sekarang, untuk setiap titik , hitung jarak dari ke setiap titik jangkar. Menggunakan triangulasi dan jarak ini, Anda dapat menghitung lokasi relatif terhadap jangkar poin dan dengan demikian koordinat untuk . Lakukan ini untuk setiap titik non-jangkar $d+1$ $P$ $P$ $P$ $P$ $P$ . Sekarang Anda memiliki koordinat untuk setiap titik, dan Anda dapat menggunakan koordinat itu untuk menemukan titik pusat tanpa meminta oracle untuk memberi Anda jarak berpasangan lagi. Saya tidak tahu apakah langkah terakhir ini dapat dilakukan lebih cepat dari waktu , tetapi hal itu dapat dilakukan tanpa mengukur lagi jarak berpasangan. $O(n^2)$

DW
sumber

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

n

$n$

@DW Terima kasih - bisakah kita melakukan sesuatu yang lebih baik dalam kasus biasa? Ini dimotivasi oleh masalah dunia nyata, sehingga data cenderung 'rata-rata' (apa pun artinya).

Logistik Pintu Terbuka

@all - permintaan maaf untuk kebingungan re: metric (Saya seorang awam di CS teoritis). Fungsi jarak saya pasti mematuhi 4 kriteria untuk ruang metrik, sesuai definisi Wikipedia tentang tautan ruang metrik .

Logistik Pintu Terbuka

@OpenDoorLogistics, saya telah menambahkan satu kasus khusus di mana tampaknya mungkin untuk berbuat lebih baik.

Lihat karya Piotr Indyk tentang algoritme cepat untuk ruang metrik. ( Algoritma Sublinear untuk Masalah Ruang Metrik , dalam Prosiding STOC '99 , hal.428-434. ACM, 1999; PS ) Bagian 3 memberikan waktu linear algoritma perkiraan 1-median.

pengguna71641
sumber

Bisakah Anda memberikan ringkasan algoritma? Kami idealnya mencari jawaban lengkap, daripada tautan ke konten eksternal.

David Richerby

Permintaan maaf atas jawaban yang sangat lambat. Saya jelas tidak terlalu sering memeriksa StackExchange. Saya pikir itu akan memakan waktu lebih dari satu jam untuk menulis ringkasan setengah jalan yang layak, sedangkan makalah Piotr ditulis dengan indah, menjelaskan algoritmanya dengan sangat jelas, dan memiliki semua definisi tepat di sebelahnya. Jadi saya pribadi akan sangat menyarankan memanfaatkan konten eksternal berkualitas tinggi ini, daripada konten internal berkualitas menengah yang dapat saya hasilkan. Jawaban singkatnya adalah: Jika Anda hanya ingin mencari median perkiraan, Anda dapat melakukannya dalam waktu linier O (n).

user71641