Contoh di mana wawasan dari geometri berguna untuk menyelesaikan sesuatu yang sepenuhnya non-geometris

28

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 dalam 3-d, yang kemudian dapat dipecahkan dengan menggunakan intuisi kita tentang ruang. Hal ini tampaknya menunjukkan bahwa kadang-kadang mungkin untuk memecahkan masalah yang sepenuhnya non-geometris menggunakan teknik dari geometri. Adakah yang tahu contoh seperti itu?

Tentu saja, istilah 'geometris' dan 'non-geometrik' agak kabur di sini. Orang dapat berargumen bahwa masalah geometris sebenarnya non-geometrik jika Anda mengganti semua titik dengan koordinatnya. Namun secara intuitif, definisi tersebut jelas. Anggap saja kita menyebut sesuatu geometris jika kita ingin mengirim makalah tentang hal itu ke SoCG.

Vinayak Pathak
sumber
3
Tentu saja kakek buyut ini adalah pendekatan P vs NP yang diuraikan oleh Mulmuley, yang murni geometris. Tapi itu belum terbukti bermanfaat. Bukti yang memisahkan P dari NC tanpa operasi bitwise adalah bukti non-geometris yang menggunakan argumen geometrik. Saya akan menambahkannya, tetapi saya sudah memberikan terlalu banyak jawaban :)
Suresh Venkat
banyak contoh seperti itu dapat ditemukan di bagian bukti tanpa kata-kata dari American Mathematical Monthly
Arjang

Jawaban:

24

Beberapa contoh lagi:

Sleator, Thurston dan Tarjan menggunakan representasi geometrik pohon sebagai partisi dari poligon, dan geometri hiperbolik, untuk membuktikan batas bawah untuk rotasi pohon biner . (Juga, saya percaya sejarah pohon pencarian biner dinamis dapat direpresentasikan sebagai tetrahedralization.)

Pengurangan nenek moyang yang paling tidak umum untuk menjawab pertanyaan minimum , karena Berkman dan Vishkin, mengaitkan masalah struktur data pada pohon dengan masalah geometri yang bisa dibilang. (dan terima kasih untuk artikelnya David)

Pengurangan masalah penjadwalan ke max berat independen set sumbu-paralel persegi panjang [1] atau pengurangan masalah penjadwalan yang berbeda untuk penutup himpunan geometris [2] mungkin memenuhi syarat.

Pengurangan masalah urutan umum terbesar untuk menemukan lapisan maxima sudah terkenal (artinya, saya terlalu malas untuk mencari siapa yang benar-benar memikirkannya).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor dan Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. Geometri Penjadwalan, FOCS 2010.

[belakangan diedit] Beberapa kasus lagi di mana tampilan "geometris" tampak mengejutkan (meskipun "penyerahan ke SoCG" atau "membuat sesuatu untuk divisualisasikan" standar mungkin tidak terpenuhi):

topologi aljabar diterapkan pada batas bawah untuk komputasi terdistribusi

menggabungkan kemampuan komputasi ke dalam dimensi Hausdorff

mendefinisikan gagasan jarak untuk kelompok, lalu volume, lalu pertumbuhan volume sebagai fungsi jarak, lalu menggunakan "pertumbuhan polinomial"

Ken Clarkson
sumber
2
Makalah Nikhil adalah contoh yang sangat menarik, yang entah bagaimana saya lupakan.
Sasho Nikolov
3
Selamat datang di cstheory, Ken :)
Suresh Venkat
1
Sepertinya tidak ada yang menyebutkan teorema pemisah planar ... Yang ternyata merupakan konsekuensi mudah dari teorema Koebe.
Sariel Har-Peled
2
Saya terkejut tidak ada yang menyebutkan kesetaraan optimasi dan pemisahan untuk pemrograman linier dan dampaknya pada optimasi kombinatorial. Buku Grotschel, Lovasz dan Schrijver berjudul "Algoritma Geometris dan Optimalisasi Kombinatorial".
Chandra Chekuri
1
Dua makalah penting yang berkaitan dengan topologi aljabar dengan komputasi terdistribusi (yang memenangkan Hadiah Gödel 2004) adalah: * Maurice Herlihy dan Nir Shavit, "Struktur Topologi Kompabilitas Asinkron," JACM 46, 6 (1999). * Michael Saks dan Fotios Zaharoglou, "Perjanjian Bebas Tunggu k-Set Tidak Mungkin: Topologi Pengetahuan Publik," SIAM J. Computing 29, 5 (2000).
Diego de Estrada
15

Tentu saja jawaban yang jauh lebih baik daripada jawaban saya sebelumnya adalah penggunaan teori penyisipan metrik untuk menyelesaikan pemotongan paling jarang. Sebuah langkah penting dalam solusi untuk masalah cut sparsest adalah realisasi bahwa hal itu bisa didekati dengan mencari embedding baik dari metrik umum menjadi ruang -normed1 .

Suresh Venkat
sumber
Bisakah Anda mengutip kertasnya?
pengguna
1
@ pengguna di sini Anda pergi.
Suresh Venkat
12

Itu disebutkan di tempat lain juga, tetapi contoh yang saya suka adalah ini: menyortir dengan informasi parsial adalah masalah menemukan ekstensi linear tetap yang tidak diketahui dari poset, mengingat poset dan menggunakan jumlah pertanyaan perbandingan sedekat mungkin dengan informasi teoretis batas bawah (ini hanya menyortir ketika jumlah perbandingan adalah ukuran kompleksitas kritis dan beberapa perbandingan diberikan secara gratis). Keberadaan strategi perbandingan yang optimal (hingga konstan) dibuktikan oleh Saks dan Kahn menggunakan sifat-sifat ordo polytope, sebuah polytope khusus yang terkait dengan poset (Anda dapat menemukan eksposisi hebat dalam buku Matousek's Lectures on Discrete Geometry book). The pertama algoritma waktu polinomial (oleh Kahn dan Kim) yang menghitung strategi perbandingan yang optimal (hingga konstan) sekali lagi menggunakan sifat-sifat polytope orde serta polytope set yang stabil dari grafik yang tidak dapat dibandingkan dari poset input.

Sasho Nikolov
sumber
11

Ada makalah yang relatif baru oleh Demaine et al yang menggunakan representasi geometris pohon pencarian biner untuk memajukan keadaan seni pada optimalitas dinamis. Saya menjadi sedikit kabur di sini karena mereka tidak menyelesaikan dugaan DO: tetapi mereka memperkuat beberapa batasan dan memberikan beberapa wawasan baru yang tampaknya berasal dari formulasi geometris.

Suresh Venkat
sumber
11

Saya rasa tidak ada contoh hal-hal seperti itu. Kecuali untuk pemrograman linier, pemrograman semi-pasti, bilangan kompleks, sebagian besar pembelajaran mesin, dll. Pertanyaan sebenarnya adalah http://www.youtube.com/watch?v=ExWfh6sGyso .

Sariel Har-Peled
sumber
5
jawaban apa pun yang melibatkan Monty Python pantas mendapat poin ekstra :)
Suresh Venkat
9

Ada makalah yang bagus di POPL tahun lalu, EigenCFA: Mempercepat analisis aliran dengan GPU , yang mewakili istilah lambda sebagai matriks dan kemudian menggunakan GPU untuk secara cepat melakukan analisis aliran data pada mereka.

Makalah ini tidak menunjukkan hal ini secara eksplisit, tetapi apa yang mereka lakukan pada dasarnya adalah mengeksploitasi struktur kategorikal ruang vektor untuk mewakili pohon. Yaitu, dalam teori himpunan biasa, pohon (dengan ketinggian tertentu) adalah persatuan terpisah dari produk-produk kartesius.

Namun, ruang vektor juga memiliki produk dan penjumlahan langsung, sehingga Anda dapat mewakili pohon sebagai elemen ruang vektor yang sesuai. Selain itu, produk langsung dan jumlah langsung bertepatan untuk ruang vektor - yaitu, mereka memiliki representasi yang sama. Ini membuka pintu untuk implementasi paralel: karena representasi fisiknya sama, banyak percabangan dan pengejaran penunjuk dapat dihilangkan.

Ini juga menjelaskan mengapa analisis aliran data adalah waktu kubik: ini menghitung vektor eigen!

Neel Krishnaswami
sumber
Apakah Anda memiliki contoh lain di mana trik pohon ke ruang vektor digunakan? Makalah EigenCFA membutuhkan terlalu banyak latar belakang untuk dipahami.
Chao Xu
Jika saya mengerti dengan benar, relasi pohon / vektor hanya mengubah pohon menjadi vektor dengan mendaftar label traversal preorder dari pohon?
Chao Xu
8

Dalam jaringan, router menggunakan TCAM (memori yang bisa dialamatkan konten terner - dengan kata lain, memori yang bisa dialamatkan konten dengan sedikit tidak peduli) untuk mengklasifikasikan lalu lintas. Entri dalam TCAM seringkali merupakan aturan pencocokan awalan multidimensi: misalnya, (101 *, 11 *, 0 *) cocok dengan paket apa pun di mana bidang header pertama dimulai dengan 101 dan bidang header kedua dimulai dengan 11 (dan lain-lain) Jika sebuah paket tidak cocok dengan aturan pertama, ia melanjutkan ke yang kedua, dan seterusnya sampai aturan yang cocok ditemukan.

dRd+1d+1Rd+1dd+1

Untuk orang-orang yang berjejaring, interpretasi ini berguna untuk memahami apa yang dilakukan seperangkat aturan tertentu. Bagi para ahli teori, ada kegunaan lain yang menarik. Menurut Algoritma untuk Klasifikasi Paket oleh Gupta dan McKeown, interpretasi geometris memungkinkan kita untuk dengan cepat menetapkan batas bawah dan atas untuk masalah klasifikasi paket. Saya tahu bekerja pada minimisasi aturan TCAM (menemukan jumlah aturan terkecil yang mempertahankan semantik) juga mendapat manfaat dari pendekatan geometris. Ada banyak referensi yang bisa saya berikan untuk ini, tetapi salah satu yang paling bermanfaat bagi Anda adalah Applegate, et al. SODA 2007 paper Mengkompresi gambar bujursangkar dan meminimalkan daftar kontrol akses. Mereka membuktikan bahwa meminimalkan varian yang lebih umum dari aturan pencocokan awalan di atas adalah NP-hard, dan menghubungkannya (lagi) ke gambar cantik persegi panjang untuk menyelesaikan masalah!

Christopher Monsanto
sumber
8

Saya terkejut tidak ada yang mengatakan Algoritma Euclidean untuk menemukan faktor umum terbesar antara dua angka. Anda dapat mengatasi masalah dengan menggambar persegi panjang axb, kemudian membagi persegi panjang dengan persegi yang dibuat oleh sisi terkecil, ulangi untuk persegi panjang sisa, terus mengulangi untuk persegi panjang sisa sampai Anda menemukan persegi yang secara merata dapat membagi persegi panjang yang tersisa (lihat animasi gif pada halaman Algoritma Euclidean).

Cara yang cukup elegan untuk mencoba mencari tahu cara kerjanya, IMO.

Doug T.
sumber
3
Saya pikir Euclid akan berpendapat bahwa angka tidak memenuhi syarat sebagai "sama sekali non-geometrik"!
Jeffε
7

Mungkin ada terlalu banyak contoh untuk dicantumkan, tetapi satu contoh klasik (disorot oleh Aigner dan Ziegler sebagai " Bukti dari Buku ") adalah penggunaan oleh Lovász dari representasi geometris untuk memecahkan masalah dalam kapasitas Shannon. Meskipun buktinya diterbitkan pada tahun 1979 dan memecahkan pertanyaan terbuka dari tahun 1956, ini tetap canggih.

RJK
sumber
6

Hubungan kode koreksi kesalahan dengan kisi-kisi, pengemasan sphere dll. (Mis., Buku Conway dan Sloane). Namun hubungannya sangat kuat, sehingga tidak cukup jelas, jika saya harus memanggil kode koreksi kesalahan "benar-benar tidak geometris" setelah itu ...

Alex 'qubeat'
sumber
4

Teknik reduksi kisi, seperti LLL atau PSLQ , sangat geometris dan memecahkan masalah teori bilangan murni, seperti pendekatan Diophantine linier dan deteksi hubungan bilangan bulat.

ZZ

pengguna834
sumber
1

kk

Tentu saja, buktinya lebih topologis daripada geometris, tetapi dalam dimensi rendah ia memiliki gambaran geometris yang jelas. Sepengetahuan saya, tidak ada bukti kombinatorial murni (yaitu bukti yang dapat Anda jelaskan kepada seseorang yang menolak untuk mendengar apa pun tentang topologi) ada.

Andrew Ryzhikov
sumber
-1

Dukungan mesin vektor dalam pembelajaran mesin mungkin memenuhi syarat.

mirror2image
sumber
-2

Ada teknik geometri komputasi untuk menyelesaikan pemrograman linear. Komputasi geometri: algoritma dan aplikasi memiliki bab yang bagus dan sederhana tentang itu.

Luca Zanetti
sumber
2
Tetapi pemrograman linier - "Temukan titik terendah dalam polyhedron ini" - secara eksplisit berbentuk geometris.
Jeffε
-3

Sebuah Integral Pasti fungsi dapat direpresentasikan sebagai daerah ditandatangani daerah yang dibatasi oleh grafik-nya.

George Polevoy
sumber
4
Benar, kecuali bahwa "dapat direpresentasikan sebagai" harus dieja "adalah".
Jeffε