Menemukan kumpulan titik terbesar dengan diameter terbatas

Diberikan poin dalam dan jarak menemukan subset terbesar dari titik-titik ini sehingga jarak Euclidian tidak ada dua dari mereka melebihi . $p_1,\ldots,p_n$ $\mathbb{R}^{d}$ $l$ $l$

Apa kompleksitas masalah ini?

Dalam grafik di atas titik-titik yang memiliki keunggulan setiap kali jarak dua titik paling banyak , masalahnya setara dengan menemukan klik maksimum. Kebalikannya mungkin tidak berlaku, karena tidak setiap grafik dapat diperoleh dengan cara ini (contohnya adalah bintang untuk ). Oleh karena itu pertanyaan terkait adalah: apa yang diketahui tentang kelas grafik ini? $l$ $K_{1,7}$ $d=2$

ds.algorithms reference-request cg.comp-geom Marcus Ritt
sumber

Perhatikan bahwa jika

diperbaiki, ada algoritma P-time "sepele": karena himpunan tersebut tertutup dalam bola jari-jari

, dan tanpa kehilangan sifat umum, bola tersebut minimal (yaitu menyentuh

poin), hitung saja semua subset. Anda dapat melakukan lebih baik, tetapi dari sudut pandang kompleksitas, masalahnya adalah "mudah".

d

$d$

l / 2

$l/2$

d + 1

$d+1$

Suresh Venkat

Saya tidak berpikir itu benar bahwa set optimal harus tertutup dalam bola jari-jari l / 2. Dalam bidang, misalnya, tiga simpul segitiga sama sisi panjang l tidak begitu tertutup.

David Eppstein

ah benar tetapi enumerasi harus bekerja terlepas.

Suresh Venkat

Anda dapat menghitung subset di dalam bola, tetapi jika Anda membuat jari-jari l / 2 maka Anda tidak akan menemukan beberapa subset berdiameter rendah, dan jika Anda membuat jari-jari lebih tinggi dari itu, maka tidak jelas bagaimana memotong subset ke bawah sehingga mereka memiliki diameter rendah.

David Eppstein

mengapa saya tidak bisa menghitung himpunan bagian, menemukan bola min melampirkan, dan menghitung kardinalitas dalam untuk masing-masing?

Suresh Venkat

Jawaban:

Ada algoritma waktu untuk versi dua dimensi dari masalah ini dalam makalah saya dengan Jeff Erickson, " Iterasi tetangga terdekat dan temukan polytopes minimal ", Disc. Comp. Geom. 11: 321-350, 1994. Sebenarnya makalah ini terutama membahas masalah ganda: mengingat jumlah titik dalam subset, temukan diameter sekecil mungkin; tetapi menggunakan masalah yang Anda gambarkan sebagai subrutin. Setidaknya pada saat kami menulisnya, kami tidak tahu apa-apa subeksponensial untuk dimensi yang lebih tinggi (walaupun jika subset hanya memiliki titik di dalamnya, bagian eksponensial dapat dibuat bergantung pada daripada $O(n^3\log n)$ $k$ $k$ $n$ menggunakan teknik di kertas yang sama).

David Eppstein
sumber

Perkiraan cukup mudah jika Anda tertarik pada subset terkecil dengan diameter paling banyak . Algoritma waktu linear dengan menggunakan grid sekarang "standar". Konstanta mungkin akan menjadi sekitar . $(1+\epsilon)l$ $2^{O(1/\epsilon^d)}$

Ada beberapa pekerjaan untuk menemukan bola terkecil yang mengandung titik k, tetapi masalah diameternya lebih sulit. Untuk melihat alasannya, titik awal yang baik adalah kertas Clarkson-Shor untuk menghitung diameter dalam 3d.

BTW, untuk dimensi tinggi, masalah bola diperkirakan dalam eksponensial waktu dalam (atau kebisingan serupa), dengan menggunakan coreset (tetapi tidak dalam dimensi!). Saya agak ragu bahwa pendekatan ini dapat diperluas untuk masalah ini, tetapi saya mungkin salah. $O(1/\epsilon^2)$

Sariel Har-Peled
sumber