Jumlah Minkowski dari dua set vektor diberikan olehA,B∈RdA,B∈RdA, B \in R^d A⊕B={a+b∣a∈A,b∈B}A⊕B={a+b∣a∈A,b∈B} A \oplus B = \{ a + b \mid a \in A, b \in B \} Saya baru saja mendengar masalah yang menarik (dikaitkan dengan Dan Halperin): Diberi bentuk , apakah ada bentuk A sehingga A ⊕ A = B...
Biarkan menjadi grafik dengan sisi positif (berbobot). Saya ingin mendefinisikan diagram Voronoi untuk satu set node / situs , untuk mengasosiasikan dengan simpul subgraph dari yang disebabkan oleh semua node ketat lebih dekat dengan daripada node lain dalam , mengukur panjang lintasan dengan...
Saya ingin meminta maaf kepada semua posting di bawah ini. Memilih forum yang salah untuk memposting ini pada awalnya. Namun alih-alih membuat ini sia-sia saya telah mengolah pertanyaan menjadi masalah "Theoretical Computer Science" yang sebenarnya. Masalah: Buat algoritme yang mengambil...
Dalam Fasilitas berkapasitas Lokasi Masalah (CFLP) , kita diberi satu set klien dan satu set fasilitas potensial . Setiap klien memiliki permintaan yang harus dilayani oleh satu atau lebih fasilitas terbuka. Setiap fasilitas memiliki biaya pembukaan dan memiliki kapasitas , yang merupakan...
Untuk aplikasi pembelajaran mesin, kebutuhan kelompok saya untuk menghitung jarak Euclidean ke th tetangga terdekat di set X untuk setiap x ∈ ( X ∪ Y ) ⊂ R d (untuk d antara 5 dan sekitar 100, dan | X | ≈ | Y | beberapa ratus hingga beberapa juta). Kami saat ini menggunakan pendekatan brute force O...
Ini masalah tetangga terdekat. Diberikan real (sangat besar !), Plus target real , cari dan yang paling dekat dengan . Kami mengizinkan pra-pemrosesan / pengindeksan yang dari (hingga ), tetapi pada waktu kueri (diberikan ), hasilnya harus dikembalikan dengan sangat cepat (misalnya, waktu). n p a...
Misalkan saya memiliki poin dalam R d . Ini menginduksi diagram Voronoi. Jika saya menetapkan masing-masing k menunjuk label ± , ini menginduksi fungsi biner pada R d . Pertanyaan: berapakah dimensi VC dari semua fungsi biner yang mungkin diinduksi oleh beberapa titik k dan beberapa pelabelan...
Dalam [1], Garey et al. mengidentifikasi apa yang kemudian dikenal sebagai Jumlah Masalah Roots Square dalam rangka menyelesaikan NP-Euclidean TSP. Mengingat bilangan bulat a1,a2,…,ana1,a2,…,ana_1, a_2, \ldots, a_n dan LLL , menentukan apakah a1−−√+a2−−√+⋯+an−−√<La1+a2+⋯+an<L\sqrt{a_1} +...
Delaunay triangulasi dalam pesawat memaksimalkan sudut minimum dalam segitiga. Apakah hal yang sama berlaku untuk triangulasi poin Delaunay pada bola? (di sini "sudut" adalah sudut lokal di lingkungan sekitar titik di puncak). Terinspirasi oleh tetapi tidak terkait dengan pertanyaan ini di...
Saya mencari perangkat lunak untuk menghitung / memperkirakan volume polyhedra cembung dimensi tinggi. Lebih khusus, saya tertarik pada sebuah program, yang dapat menangani tubuh dengan simpul dalam ruang d- dimensi dengan parameter yang dibatasi kira-kira sebagai berikut: d ≤ 50 dan n ≤ 1000 ....
Saya bekerja di bidang teknik struktural dan saya ingin menemukan algoritma yang efisien untuk membangun perkiraan (dalam metrik Hausdorff) dari tubuh cembung KKK oleh cembung cembung ellipsoid, untuk beberapa tetap . Saat ini saya hanya bekerja di dimensi 2 dan 3.nnnnnn Gagasan pertama saya...
Saya mencari algoritme untuk menggambar grafik gabungan / ketergantungan (untuk aplikasi linguistik). Grafik seperti itu akan memiliki dua jenis simpul yang berbeda (token, node), dan dua jenis tepi yang berbeda (hierarkis, non-hierarkis). Saya baru mengenal teori grafik dan algoritma secara umum,...
Saya kesulitan menemukan algoritme atau menerbitkan makalah tentang triangulasi poligon bersilangan (juga poligon dengan struktur lubang). Bisakah ada yang memandu saya untuk menemukan makalah / algoritma yang dipublikasikan? PS: tolong beri tag pada seseorang pertanyaan ini dengan tepat, saya...
Biarkan menjadi satuan persegi. Sebagai fungsi dari , berapakah jumlah maksimum dari -fat berpasangan-berpisah dengan diameter setidaknya 1 yang dapat memotong ?SSSββ\betaββ\betaSSS Di bawah, kami memberikan angka yang menunjukkan bahwa untuk , jumlah maksimumnya adalah 7. Bagaimana dengan...
Saya mencari dimensi VC dari sistem set berikut. Universe sedemikian rupa sehingga U ⊆ R 3 . Dalam sistem himpunan R, setiap himpunan S ∈ R berkorespondensi dengan sphere dalam R 3 sehingga himpunan S mengandung elemen dalam U jika dan hanya jika sphere yang sesuai berisinya dalam R 3 .U= { p1,...
Fungsi linear dalam satu variabel memiliki dimensi VC = 3 dan saya ingat pernah membaca bahwa VC untuk polinomial derajat adalah .( d 2 + 3 d + 2 ) / 2ddd( d2+ 3 d+ 2 ) / 2(d2+3d+2)/2(d^2 + 3d + 2)/2 Saya mencari ide yang dapat membuktikan klaim di atas (dan mungkin menggeneralisasi ke banyak...
Sunting: Saya pikir semangat pertanyaan itu baik, tetapi perlu ditingkatkan. Asumsi yang dibuat untuk lemparan koin membuat pertanyaan itu sepele, dan die roll masih belum cukup jelas. Apa asumsi yang masuk akal yang dapat kita buat tentang die roll yang membuat pertanyaan itu bisa diterima,...
Apa hasil yang paling dikenal untuk struktur data yang menawarkan operasi berikut pada set poin dalam ruang euclidean 2 dimensi: i n s e r t ( x )insert(x)insert(x) de l e t e ( x )delete(x)delete(x) (di mana k adalah bilangan bulat lebih besar dari 0) mengembalikantitik terdekat k ke x yang...
Lemma pemotongan (lemma penguraian sel) menyatakan bahwa diberi garis dalam bidang dimungkinkan untuk membaginya menjadi daerah (bahkan segitiga) untuk setiap sehingga interior setiap wilayah berpotongan dengan garis . Untuk lebih lanjut lihat misalnya buku Matousek's Lectures on Discrete Geometry...
Sebuah -net untuk ruang rentang adalah bagian dari sehingga tidak kosong untuk semua sehingga.( X , R ) N X N ∩ R R ∈ R | X ∩ R | ≥ ε | X |εε\varepsilon(X,R)(X,R)(X,\mathcal{R})NNNXXXN∩RN∩RN\cap RR∈RR∈RR\in \mathcal{R}|X∩R|≥ε|X||X∩R|≥ε|X||X\cap R| \ge \varepsilon |X| Diberi jarak ruang dari...