Menyortir berdasarkan jarak Euclidean

$S$ adalah seperangkat poin di pesawat. Titik acak diberikan pada bidang yang sama. Tugasnya adalah untuk mengurutkan semua dengan jarak Euclidean antara dan . $x \notin S$ $y \in S$ $x$ $y$

Pendekatan tanpa otak adalah menghitung jarak antara dan untuk semua dan kemudian mengurutkannya menggunakan algoritma cepat apa pun. $x$ $y$ $y \in S$

Apakah ada cara untuk menyimpan atau preproses sehingga proses penyortiran menjadi lebih cepat? $S$

cg.comp-geom sorting Alex K.
sumber

Anda dapat mempertimbangkan kisi dengan ukuran dan titik grup yang sesuai dengan kotak yang sesuai (menggunakan, katakanlah, tabel hash). Kemudian untuk pasangan kotak tertentu, Anda dapat menyimpulkan bahwa semua titik dari satu kotak lebih jauh dari

daripada semua titik dari kotak lain. Dalam praktiknya itu bisa membantu, saya kira.

x

$x$

ilyaraz

"Pendekatan tanpa otak" yang Anda nyatakan berjalan dalam waktu O (n log n), di mana n adalah jumlah poin dalam S, yang saya kira cukup cepat dalam praktiknya. Apakah Anda ingin menyingkirkan faktor log, atau Anda ingin sesuatu yang lain seperti penyortiran eksternal ?

Tsuyoshi Ito

Intinya adalah bahwa saya memiliki waktu yang hampir tidak terbatas untuk menyiapkan set poin saya, tetapi waktu untuk mengurutkan mereka sangat terbatas. Yang mengatakan, setiap mempercepat penyortiran standar dihargai - bahkan jika itu sama O (n log n), tetapi lebih cepat dalam kasus terburuk (atau kasus terbaik, atau apa pun).

Alex K.

Misalnya, jika saya menyimpan S sebagai pohon 2-d, saya dapat menemukan tetangga terdekat dalam waktu O (log n). Mungkin ada solusi serupa untuk tugas saya. Saya bukan ahli hebat dalam struktur data spasial - dan ada banyak sekali - saya bisa dengan mudah melewatkannya.

Alex K.

Jawaban:

Solusi 1: Temukan garis-garis tegak lurus antara pasangan titik, dan buat susunan garis-garis ini. Susunan memiliki sel, di mana urutan yang diurutkan adalah konstan. Jadi buat struktur data lokasi titik untuk pengaturan, dan hiasi setiap sel dengan urutan yang akan dikembalikan untuk poin dalam sel itu. Pesanan yang diurutkan antara sel yang berdekatan hanya berbeda dalam satu transposisi, sehingga Anda dapat menggunakan struktur data yang persisten untuk memungkinkan representasi dari pesanan yang diurutkan ini untuk berbagi ruang. Total ruang adalah dan waktu kueri adalah $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

Solusi 2: Pilih sampel acak dari garis-garis tegak lurus yang sama ini, buat susunannya, dan pisahkan setiap sel susunan dengan segmen garis vertikal melalui masing-masing persilangan dua garis sampel. Partisi yang dihasilkan memiliki sel, yang masing-masing dengan probabilitas tinggi dilintasi oleh tidak terbagi dua. Hiasi setiap sel partisi dengan urutan poin yang diurutkan dari beberapa x di dalam sel. Total ruang adalah . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

Sekarang, untuk melakukan kueri, cari titik kueri di partisi, cari pemesanan yang disimpan dengan sel partisi, dan gunakan algoritma penyortiran perbandingan pohon Cartesian dari Levcopoulos & Petersson (1989) dimulai dengan pemesanan yang disimpan ini. Waktu untuk langkah ini sebanding dengan di mana adalah jumlah poin yang out-of-order dengan titik . Tapi adalah (masing-masing bistor yang tidak di -ampleksi menyebabkan paling banyak satu pasang poin yang tidak berurutan), jadi waktu permintaan $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ juga . $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
sumber

PS berikut ini adalah varian alternatif dari solusi 2 yang menggunakan ruang dan waktu permintaan yang sama tetapi memperdagangkan algoritma preprocessing yang lebih rumit untuk algoritma kueri yang lebih sederhana: 11011110.livejournal.com/233793.html

David Eppstein

Mengapa

pre-processing ketika Anda bisa mengurutkan dari semua

titik awal dalam waktu

dan menyimpan hasilnya dalam tabel hash menggunakan ruang

untuk pencarian konstan?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Karena ada

titik awal dengan urutan pesanan yang berbeda, bukan

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein

Anda mungkin tidak akan bisa keluar dari kapan pun Anda mengirisnya; bahkan wilayah precomputing yang sesuai dengan semua kemungkinan sortir pesanan dapat (saya percaya) menghasilkan wilayah dan dengan demikian menemukan wilayah 'Anda' dengan teknik pencarian yang berarti akan mengambil waktu. ( EDIT: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(n))$ ini benar-benar salah; lihat jawaban David Eppstein yang luar biasa untuk informasi lebih lanjut!) Salah satu cara yang berguna untuk mengurangi kerumitan, di sisi lain - terutama jika Anda tidak memerlukan pengurutan penuh sekaligus tetapi hanya perlu untuk dapat secara acak mengeluarkan -terdekat on the fly - mungkin melalui diagram Voronoi tingkat tinggi: ekstensi sel Voronoi standar yang mengakomodasi tidak hanya tetangga terdekat tetapi juga yang terdekat kedua, dll. Makalah Frank Dehne tentang pencarian k-tetangga terdekat, http: //people.scs .carleton.ca / ~ dehne / publikasi / 2-02.pdf tampaknya menjadi referensi kanonik; beranda di http://www.dehne.carleton.ca/publications memiliki sejumlah makalah lain tentang diagram Voronoi yang mungkin bermanfaat. $k$

Steven Stadnicki
sumber

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@ David Saya pikir Anda harus membuat ini jawaban.

James King

Diperbantukan - n! merasa salah ketika saya menulisnya, tetapi saya tidak bisa melihat kasus yang menentang. Saya akan segera mengubah jawaban saya untuk memperbaikinya, tetapi saya benar-benar ingin melihat jawaban yang lebih langsung; Terima kasih!

Steven Stadnicki