Pertanyaan yang diberi tag «cg.comp-geom»

Computational Geometry adalah studi tentang masalah geometris dari perspektif komputasi. Contoh masalah termasuk: perhitungan benda-benda geometris seperti convex hulls, reduksi dimensionalitas, masalah jalur terpendek dalam ruang metrik, atau menemukan subset kecil dari titik-titik yang mendekati beberapa ukuran dari keseluruhan set (yaitu coreset).

Masalah Super Mario Galaxy
Misalkan Mario sedang berjalan di permukaan sebuah planet. Jika dia mulai berjalan dari lokasi yang diketahui, ke arah yang tetap, untuk jarak yang telah ditentukan, seberapa cepat kita dapat menentukan di mana dia akan berhenti? PPPsssPPPvvvpppℓℓ\ellPPPPPP PPPsssvvvℓℓ\ell PPPO(1)O(1)O(1)ℓℓ\ellPPP (Dalam praktiknya, panjang jalur sebenarnya tidak terikat; ada batas atas global dalam …


Apa alasan para peneliti dalam komputasi geometri lebih memilih model BSS / real-RAM?
Latar Belakang Perhitungan atas bilangan real lebih rumit daripada perhitungan atas bilangan alami, karena bilangan real adalah objek tak terhingga dan ada banyak bilangan real, oleh karena itu bilangan real tidak dapat dengan setia diwakili oleh string berhingga pada alfabet terbatas. Berbeda dengan komputasi klasik atas string hingga di mana …



Contoh di mana wawasan dari geometri berguna untuk menyelesaikan sesuatu yang sepenuhnya non-geometris
Salah satu hal yang menyenangkan tentang berevolusi di alam semesta dengan tiga dimensi spasial adalah bahwa kita telah mengembangkan keterampilan pemecahan masalah yang berkaitan dengan objek di ruang angkasa. Jadi, misalnya, kita dapat menganggap triplet angka sebagai titik dalam 3-d dan karenanya perhitungan tentang triplet angka sebagai perhitungan tentang titik …

Embedding isometrik dari L2 ke L1
Hal ini diketahui bahwa diberi nnn bagian-titik dari ℓd2ℓ2d\ell_2^d (yang, diberikan nnn poin di RdRd{\mathbb R}^d dengan jarak Euclidean) adalah mungkin untuk menanamkan mereka isometrically di .ℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 Apakah isometri dapat dihitung pada waktu polinomial (mungkin, acak)? Karena ada masalah ketepatan hingga, pertanyaan tepatnya adalah Diberikan satu set XXX dari …



Kemasan persegi panjang menjadi poligon cembung tetapi tanpa rotasi
Saya tertarik pada masalah pengemasan salinan identik persegi panjang (2 dimensi) menjadi cembung (2 dimensi) poligon tanpa tumpang tindih. Dalam masalah saya, Anda tidak diperbolehkan memutar persegi panjang dan dapat mengasumsikan bahwa mereka berorientasi paralel dengan sumbu. Anda hanya diberi dimensi persegi panjang dan simpul poligon dan ditanya berapa banyak …

Mendeteksi dua jenis poligon yang hampir sederhana
Saya tertarik pada kerumitan dalam memutuskan apakah poligon non-sederhana yang diberikan hampir sederhana, dalam salah satu dari dua pengertian formal yang berbeda: lemah sederhana atau tidak menyilang sendiri . Karena istilah-istilah ini tidak dikenal secara luas, izinkan saya mulai dengan beberapa definisi. PPPp0,p1,p2,…,pn−1p0,p1,p2,…,pn−1p_0, p_1, p_2, \dots, p_{n-1}pipip_ipipi+1modnpipi+1modnp_i p_{i+1\bmod n} Poligon …


Set disjoint maksimum: apa faktor perkiraan sebenarnya dari algoritma serakah?
Pertimbangkan masalah menemukan set disjoint maksimum - set maksimum bentuk geometris yang tidak tumpang tindih, dari koleksi kandidat tertentu. Ini adalah masalah NP-complete, tetapi dalam banyak kasus, algoritma serakah berikut menghasilkan perkiraan faktor konstan: Untuk setiap bentuk kandidat x , hitung angka perpotongan disjointnya = jumlah terbesar dari bentuk disjoint …


Struktur data untuk kueri titik produk minimum
RnRn\mathbb{R}^n⟨⋅,⋅⟩⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmmv1,v2,…,vmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx∈Rnx \in \mathbb{R}^nmini⟨x,vi⟩mini⟨x,vi⟩\min_i \langle x, v_i \rangleO(nm)O(nm)O(nm)O ( log 2 m )n=2n=2n = 2O(log2m)O(log2⁡m)O(\log^2 m) Satu-satunya hal yang bisa saya pikirkan adalah sebagai berikut. Ini adalah konsekuensi langsung dari lemma Johnson-Lindenstrauss bahwa untuk setiap dan distribusi pada ada pemetaan linear (yang dapat dievaluasi dalam …

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.