Apa yang diketahui tentang masalah berikut? Diberikan kumpulan fungsi f : { 0 , 1 } n → { 0 , 1 } , temukan subkoleksi terbesar S ⊆ C tunduk pada kendala bahwa VC-Dimensi ( S ) ≤ k untuk beberapa bilangan bulat k .CCCf:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆CS⊆CS \subseteq...
Masalah galeri seni tradisional membuat suatu daerah dan penjaga dengan beberapa pandangan tentang visibilitas, dan meminta jumlah penjaga minimum yang perlu ditempatkan untuk melihat seluruh wilayah. Adakah yang pernah melihat varian galeri seni di mana wilayah visibilitas ditentukan oleh...
Saya mencoba untuk menutupi poligon cekung sederhana dengan persegi panjang minimum. Persegi panjang saya bisa panjang, tetapi memiliki lebar maksimum, dan poligon tidak akan pernah memiliki sudut yang akut. Saya berpikir tentang mencoba menguraikan polong cekung saya menjadi segitiga yang...
Diberikan dua himpunan bagian dari hypercube dimensional (yaitu, M , N ⊆ { 0 , 1 } d ), saya mencari algoritma yang mengambil titik m ∈ M , n ∈ N pada jarak hamming (atau L 1 - jarak pada hypercube) d H ( m , n ) minimal. Algoritma naif yang memeriksa hanya setiap pasangan membutuhkan | M | ⋅ | N |...
Input: Satu set poin dalam , dan integer .R 3 k ≤ nnnnR3R3\mathbb{R}^3k ≤ nk≤nk \le n Output: Kotak pembatas sumbu-rata volume terkecil yang berisi setidaknya dari poin ini.nkkknnn Saya ingin tahu apakah ada algoritma yang dikenal untuk masalah ini. Yang terbaik yang bisa saya pikirkan adalah...
Lemma Johnson-Lindenstrauss mengatakan secara kasar bahwa untuk setiap koleksi SSS dari nnn poin dalam RdRd\mathbb{R}^d , terdapat peta f:Rd→Rkf:Rd→Rkf:\mathbb{R}^d \rightarrow \mathbb{R}^k mana k=O(logn/ϵ2)k=O(logn/ϵ2)k = O(\log n/\epsilon^2) sedemikian rupa sehingga untuk semua x,y∈Sx,y∈Sx, y...
Diberikan satu set pesawat terbang yang ditentukan oleh vektor normal , tipe selnya (atau tanda vektor) adalah semua vektor t ∈ { + , - } m yang terdapat vektor v ∈ R d sehingga ⟨ v , h i ⟩ ≠ 0 dan t i = tanda ( ⟨ v , h i ⟩ )h1,…,hm∈Rdh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf...
Menurut buku Teori Topologi Grafik oleh Gross dan Tucker, diberikan embedding seluler grafik pada suatu permukaan (dengan 'permukaan' yang saya maksudkan adalah bola dengan beberapa pegangan, dan di bawah S n mengacu pada bola dengan tepat n handle), seseorang dapat mendefinisikan multigraf ganda...
Pertimbangkan dua ruang metrik dan , dan embedding . Penyematan ruang metrik tradisional mengukur kualitas sebagai rasio terburuk dari asli ke jarak final: (X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow
Apakah ada pekerjaan untuk memulihkan kemiringan segmen garis dari digitalisasi? Seseorang tidak dapat melakukan ini dengan akurasi sempurna, tentu saja; apa yang diinginkan adalah metode untuk mendapatkan dari garis digital interval dari kemungkinan kemiringan. (Gagasan garis digital yang saya...
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 .o ( n 2 )nnno ( n2)o(n2)o(n^2) Ada algoritma membagi dan...
Dalam SODA 1995 , Jeff Erickson menunjukkan batas yang lebih rendah untuk kepuasan linear (memeriksa apakah beberapa subset dari bilangan real memenuhi persamaan linear pada variabel r ). Metode pembuktian menggunakan infinitesimal dan prinsip transfer Tarski .rrrnnnrrr Bisakah seseorang...
Apa batas terbaik saat ini untuk melakukan kueri penghitungan kisaran ruang setengah pada set poin dimensi, dinyatakan dalam bentuk tradeoff waktu / ruang. Menurut mani 1993 kertas Matousek ini (Teorema 6.2, pencarian Rentang dengan Efisien hirarkis Stek), kita dapat melakukan berbagai perhitungan...
Banyak di sini mungkin menyadari batas bawah super-linear baru-baru ini Alon untuk ϵϵ\epsilon jaring dalam pengaturan geometris alami [PDF] . Saya ingin tahu apa, jika ada, seperti batas bawah yang menyiratkan tentang perkiraan masalah Set Cover / Hitting Set yang terkait. Untuk sedikit lebih...
Mengingat satu set poin di ruang Euclides dimensi, masalahnya adalah untuk menentukan apakah convex hull berisi bola Unit berpusat pada titik asal.nnnddd Apakah masalah ini dalam NP? Itu dalam co-NP karena orang dapat memberikan titik di bola di luar lambung cembung sebagai saksi dan...
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...
Misalkan saya memiliki poligon sederhana dan bilangan bulat k . Apa saja pendekatan yang ada untuk menemukan jari-jari terkecil r sehingga saya bisa menutup S dengan k lingkaran jari-jari r ? Bagaimana jika r diperbaiki, dan saya ingin meminimalkan k
Diberikan satu set poin dalam ruang Cartesian 3D, saya mencari algoritma yang akan mengurutkan poin-poin ini, sehingga jarak Euclidean minimal antara dua titik berturut-turut akan dimaksimalkan. Ini juga akan bermanfaat jika algoritma memiliki kecenderungan menuju jarak Euclidean rata-rata yang...
Teorema Zone mengatakan bahwa jika kita menusuk susunan garis n dengan garis lain, kompleksitas total zonanya , himpunan semua wajah 0, 1, dan 2 yang bersebelahan dengannya adalah O (n). Konstanta yang sebenarnya adalah kira-kira 6n setidaknya seperti yang dinyatakan dalam berbagai buku teks, dan...
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...