Temukan Jarak Terpendek Berpasangan dari Poin di o (n log n)?

Latihan berikut telah dibagikan kepada siswa yang saya awasi:

Dengan titik di pesawat, buatlah algoritma yang menemukan sepasang titik yang jaraknya minimal di antara semua pasangan titik. Algoritme harus berjalan dalam waktu . $n$ $o(n^2)$

Ada algoritma membagi dan menaklukkan (relatif) sederhana yang menyelesaikan tugas dalam waktu . $\Theta(n \log n)$

Pertanyaan 1 : Apakah ada algoritma yang memecahkan masalah yang diberikan tepat pada waktu terburuk ? $\mathcal{o}(n \log n)$

Apa yang membuat saya curiga bahwa ini mungkin terjadi adalah hasil yang saya ingat pernah saya lihat dalam beberapa pembicaraan (referensi dihargai). Ini menyatakan sesuatu di sepanjang garis yang tidak lebih dari angka konstan $c \in \mathbb{N}$ titik dapat diatur dalam pesawat di sekitar beberapa titik $p$ di dalam lingkaran jari-jari $r \in \mathbb{R}$ , dengan $r$ jarak minimal antara dua titik yang terlibat . Saya pikir $c=7$ , titik-titik yang membentuk segi enam sama sisi dengan $p$ di tengah (dalam kasus ekstrim).

Dalam hal ini, algoritma berikut harus menyelesaikan masalah mereka dalam langkah $n$ .

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Perhatikan bahwa ini (diklaim sebagai) dalam waktu linier karena hanya jumlah titik yang konstan rtidak boleh jauh mdari p(dengan asumsi pernyataan di atas); hanya poin-poin ini yang harus diselidiki untuk menemukan minimum baru. Ada tangkapan, tentu saja; bagaimana Anda menerapkan nextNeighbour(mungkin dengan preprocessing dalam waktu linier)?

Pertanyaan 2 : Biarkan satu set poin dan titik . Biarkan dengan $R$ $p \notin R$ $m \in \mathbb{R}$

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

dan

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$ .

Asumsikan terbatas. Apakah mungkin untuk menemukan dengan jarak minimal dari dalam waktu (diamortisasi) ? (Anda dapat mengasumsikan dibangun dengan menambahkan titik yang diselidiki satu per satu.) $R_{p,m}$ $p' \in R_{p,m}$ $p$ $\mathcal{O}(1)$ $R$ $p$

ds.data-structures cg.comp-geom Raphael
sumber

Saya akan mengusulkan untuk mencari dengan "pasangan terdekat" sebagai kata kunci.

Yoshio Okamoto

Ini semua barang standar sekarang, lihat dua bab pertama di sini: goo.gl/pLiEO

Sariel Har-Peled

Ps. Jika Anda ingin waktu yang diharapkan, maka Anda bahkan dapat menghitung triangulasi Delaunay, yang berisi jarak minimum.

domotorp

Setelah pertanyaan 1 Anda menulis "tidak lebih dari jumlah titik konstan yang dapat diatur dalam bidang di sekitar beberapa titik p di dalam lingkaran jari-jari r, dengan r jarak minimal antara p dan titik lainnya." Ini tentu saja tidak benar: Anda dapat mengambil sejumlah titik pada lingkaran jari-jari r. Pernyataan Anda benar jika r adalah jarak minimal antara dua titik, dalam hal ini buktinya cukup sederhana.

domotorp

pertanyaan pertama adalah hal-hal buku teks, seperti yang sudah ditunjukkan: jelas bukan tingkat penelitian. saya tidak mengerti pertanyaan kedua: untuk setiap , yang Anda meminta baik tidak ada atau tetangga paling dekat dengan di . jadi bagaimana ini berbeda dari pertanyaan 1? apa yang Anda amortisasi (mis. jika ini adalah pertanyaan struktur data apa saja pembaruan dan kueri)?

m

$m$

p^{'}

$p'$

p

$p$

R

$R$

Sasho Nikolov

Jawaban:

Tidak mungkin menyelesaikan masalah dalam waktu kurang dari dalam model standar, misalnya menggunakan pohon keputusan aljabar. Ini mengikuti dari karya Yao dan Ben-Or yang menunjukkan bahwa dalam model ini tidak mungkin untuk memutuskan apakah satu set nomor input semuanya berbeda atau tidak (lihat http://people.bath.ac.uk/masnnv /Teaching/AAlg11_8.pdf ). Jika ada masalah Anda, bayangkan semuanya berada di garis nyata. Jika dua titik adalah sama, maka output Anda akan menjadi dua titik dengan jarak nol, sedangkan sebaliknya tidak, jadi solusi untuk masalah Anda juga akan menyelesaikan masalah DISTINCT NUMBERS. Jika Anda ingin menganggap bahwa semua poin Anda berbeda, maka tambahkan saja ke $cn\log n$ $n$ $i\epsilon$ $x_i$ input dari masalah DISTINCT NUMBERS, dalam hal ini jika output Anda paling banyak , maka angkanya tidak semuanya berbeda. (Meskipun dalam hal ini Anda harus menggunakan versi janji di mana perbedaan dua angka berbeda setidaknya , tapi saya pikir bukti yang sama berfungsi untuk menunjukkan bahwa Anda juga memerlukan dalam hal ini kasus.) $n\epsilon$ $2n\epsilon$ $\Omega(n\log n)$

domotorp
sumber

Memang terima kasih. Itu menjawab pertanyaan 2 (negatif) juga.

Raphael

Masalah yang Anda sebutkan tampaknya juga dikenal sebagai Elemen Perbedaan Perbedaan .

Raphael

Referensi @Sariel Har-Peled ( goo.gl/pLiEO ) menyajikan algoritma linear-waktu praktis untuk menemukan pasangan terdekat. Dokumen itu langsung membahas argumen ini, dan menjelaskan bahwa itu tidak berlaku karena algoritma menggunakan model perhitungan yang lebih kuat.

kevin cline

Ya, tetapi pertanyaannya secara spesifik menanyakan waktu kasus terburuk. Tetapi saya setuju bahwa semua pengamatan saya sudah muncul dalam tesis Sariel.

domotorp

Ada algoritma waktu linear yang diharapkan secara acak oleh Rabin; lihat misalnya Rabin Membalik Koin di blog Lipton.

David Eppstein
sumber

Seperti yang saya mengerti pertanyaan 2, algoritma Rabin menyediakan semacam jawaban untuk itu juga. Pada setiap langkah waktu struktur data adalah kisi dengan lebar sel kurang dari jarak terkecil antara pasangan titik yang terlihat sejauh ini, dibagi dengan (sehingga tidak ada sel yang mengandung lebih dari satu titik tunggal). Untuk menjawab pertanyaan dalam pertanyaan 2, Anda hanya perlu memetakan ke sel di grid dan melihat jumlah sel yang konstan di sekitarnya. Dengan analisis algoritma, jika set titik input diperiksa dalam urutan acak, daripada waktu pembaruan diamortisasi untuk grid adalah per titik baru dalam harapan. $\sqrt{2}$ $p$ $O(1)$

Sasho Nikolov
sumber

BTW saya merujuk bukan pada versi algoritma seperti yang dijelaskan Lipton, tetapi seperti yang dijelaskan dalam komentar pertama (dan buku Kleinberg dan Tardos).

Sasho Nikolov

Hanya dengan harapan, lihat jawaban domotorps.

Raphael

saya tidak melihat di mana pun Anda ingin membatasi diri Anda pada algoritma deterministik. Algoritme rabin menarik karena ia berputar di sekitar pohon keputusan batas bawah (ini mirip dengan batas bawah untuk jenis perbandingan vs algoritma pengurutan bilangan bulat). btw, mungkin ada lebih banyak yang digunakan rabin untuk berkeliling batas bawah, yaitu trik hashing yang digunakan untuk mengakses grid

Sasho Nikolov

Re "lebih banyak yang menggunakan Rabin": juga kemampuan untuk membulatkan input bilangan real ke integer. Seseorang harus sangat berhati-hati dengan ini: jika Anda membuat model perhitungan di mana seseorang dapat melakukan operasi aritmatika standar dan membulatkan bilangan real, semua dalam waktu konstan per operasi, maka dimungkinkan untuk menyelesaikan masalah PSPACE-lengkap dalam waktu polinomial dalam model ini. Tetapi Rabin hanya membulatkan angka input (ke tingkat presisi berbeda dalam iterasi yang berbeda), dan bentuk pembulatan terbatas ini tidak bermasalah.

David Eppstein

o (n \log n)

$o(n \log n)$

O (1)

$O(1)$