Memilih titik yang paling tersebar dari satu set poin

Apakah ada algoritma (efisien) untuk memilih himpunan bagian dari titik dari satu set titik ( ) sedemikian rupa sehingga mereka "menutupi" sebagian besar wilayah (di atas semua himpunan bagian ukuran )?$M$$N$$M < N$$M$

Saya berasumsi poinnya ada di bidang 2D.

Algoritme naif itu sederhana, tetapi terlalu rumit dalam hal kompleksitas waktu:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Saya mencari metode yang lebih efisien atau bahkan perkiraan.

Contoh, ini adalah pesawat dengan beberapa titik acak di dalamnya:

Untuk , saya berharap memilih poin seperti ini:$M=5$

Perhatikan titik yang dipilih (merah) tersebar di seluruh pesawat.

Saya menemukan sebuah artikel " PEMILIHAN TIPE YANG DISISFIKASI SECARA EFEKTIF UNTUK PEMASANGAN VISUAL " yang terkait dengan masalah ini. Namun, ini mengasumsikan poin tertimbang.

Berikut ini adalah solusi perkiraan. Karena N sangat besar dan M sangat kecil, bagaimana dengan yang berikut:

1. Hitung lambung cembung N
2. Pilih hingga poin M dari lambung yang memenuhi kriteria jarak maksimum Anda.
3. Jika Langkah 2 membuat Anda kurang dari titik M maka pilih 1 titik dari interior yang memaksimalkan jaraknya dari titik yang dipilih sebelumnya.
4. Ulangi Langkah 3 hingga jumlah titik yang dipilih adalah M

Intuisi di baliknya adalah bahwa sejak N >> M , dan Anda ingin titik sejauh mungkin dari satu sama lain, mereka mungkin akan mendekati tepi data, jadi Anda mungkin mulai dengan lambung dan kemudian secara iteratif bekerjalah dari sana.

Selain itu, dengan memulai dengan lambung, Anda mengurangi pencarian awal Anda dari N ke N ^1/2 .

MEMPERBARUI

Jika langkah 3 dan 4 di atas terlalu lama (karena Anda berulang kali menguji bagian dalam set data Anda), dua gagasan lagi terpikir oleh saya untuk mempercepat masalah Anda.

1. Pencarian Acak : Katakanlah Anda menemukan poin P pada lambung di Langkah 2. Kemudian secara acak gambar poin M - P dari interior. Pilih set terbaik setelah uji X.
2. Simulasi Annealing : Hitung kotak ikatan terkecil yang mencakup dataset Anda (tidak harus disejajarkan dengan sumbu, bisa dimiringkan). Kemudian tentukan satu set M titik grid yang terdistribusi secara seragam pada kotak pembatas itu. Catatan, poin-poin ini tidak selalu bertepatan dengan poin dataset Anda. Kemudian untuk setiap titik kisi temukan tetangga k- Nearest di dataset Anda. Jalankan melalui setiap kombinasi M x k dan pilih satu yang memenuhi kriteria jarak maksimum Anda. Dengan kata lain, Anda menggunakan grid awal sebagai bootstrap untuk menemukan solusi awal yang baik .

$N$$M$

$M$$M$

$M$$1$$M=3,4,5$

$M=3$$1$$M=4$$M=5$$1$

Jika kita ingin menghindari pemilihan titik yang mendominasi di pinggiran, tujuan yang berbeda akan terbukti berguna. Maksimalisasi jarak minimum antar titik adalah kriteria yang demikian. Masalah terkait telah dibahas di StackOverflow , di Computer Science SE , di Math.SE , dan di MathOverflow .

$M$$D$$M$$D$

OK, jadi Anda ingin memilih titik M dari set N poin yang diberikan dalam bidang Euclidean, sehingga jumlah jarak berpasangan dari titik yang dipilih adalah maksimal, benar?

Algoritme pencarian lokal standar cukup cepat dan menawarkan perkiraan yang cukup baik. Runtime adalah linear dalam N dan kuadratik dalam M. Rasio aproksinya adalah 1 - 4 / M Ini berarti bahwa rasio menjadi lebih baik dengan meningkatnya M. Misalnya, untuk M = 10 mendapat 60% nilai optimal, dan untuk M = 50 mendapat 92% nilai optimal.

Algoritma juga berfungsi untuk ruang Euclidean dimensi umum. Dalam hal ini, masalahnya adalah NP-hard. Tapi di pesawat, tidak diketahui apakah NP-hard.

Sumbernya adalah tulisan ini . Semoga ini membantu! Terbaik, Alfonso

Salah satu solusinya adalah:

• Buat persegi panjang pembatas di $O(n)$ waktu

• Make M artificial even distributed points inside this bounding rectangle, some M are more difficult than others. In your case four in the corners of the rectangle and one in the center

• Build a KD-Tree of your N input points. $O(n(log(n)))$

• Query each of your M points for nearest neighbor in the KD-Tree. $O(m(log(n)))$ time

The whole algorithm should be correct and is bounded to $O(n(log(n)))$. Satu-satunya bagian yang sulit adalah seperti yang dikatakan sebelum distribusi poin M buatan . Saya berasumsi bilangan prima yang lebih besar seharusnya agak sulit. Tapi saya berasumsi ada algoritma yang efisien untuk ini. Ini cukup sepele untuk$\sqrt{M} \in \mathbb{N}$, saat itu hanya grid yang perlu dihasilkan dan poinnya adalah pusat grid.