Jumlah triangulasi seperangkat poin

Setelah mendengar Emo Welzl berbicara tentang masalah ini musim panas ini, saya tahu jumlah triangulasi seperangkat poin dalam pesawat berada di antara dan . Mohon maaf jika saya ketinggalan zaman; pembaruan disambut. $n$ $\Omega(8.48^n)$ $O(30^n)$

Saya menyebutkan ini di kelas, dan ingin menindaklanjuti dengan kata-kata bijak yang singkat untuk memberi siswa pengertian tentang (a) mengapa terbukti sangat sulit untuk menentukan jumlah ini, dan (b) mengapa begitu banyak yang peduli untuk memahaminya. Saya menemukan bahwa saya tidak memiliki jawaban yang memadai untuk menjelaskan masalah tersebut; sangat banyak untuk kearifan saya!

Saya menghargai pendapat Anda tentang pertanyaan-pertanyaan yang tidak jelas ini. Terima kasih!

co.combinatorics cg.comp-geom Joseph O'Rourke
sumber

Menurut halaman poligonisasi Erik Demaine , ikatan yang dinyatakan dalam pembicaraan adalah

, tetapi saya tidak ingat apakah Emo Welzl menyatakan bahwa seseorang dapat menunjukkan ikatan yang lebih baik menggunakan analisis yang lebih cermat. Untuk beberapa alasan, saya memiliki

di kepala saya.

O (56^{n})

$O(56^n)$

O (35^{n})

$O(35^n)$

Timothy Sun

Pada halaman yang sama, ini menyatakan "Batas terbaik saat ini adalah 30". Angka 56 adalah untuk poligonisasi.

Chao Xu

Mungkin ada baiknya memberikan jawaban saya sendiri untuk pertanyaan saya. Triangulasi dibentuk oleh segmen noncrossing. Memahami ketidaksesuaian itu sulit. Itu (a). Untuk (b), pengejaran didorong oleh mencoba memahami non-lintas. Saya pikir Anda akan setuju bahwa jawaban ini tidak memadai.

Joseph O'Rourke

Sebagai acuan, melakukan hal yang sama untuk poin dalam posisi cembung adalah latihan pekerjaan rumah melalui angka Catalan. Ini karena kita dapat mengkarakterisasi ketidak-silangan dengan cara yang baik melalui tanda kurung yang seimbang (memberi kepercayaan pada poin (a))

Suresh Venkat

Saya cenderung mengatakan bahwa masalah ini tidak terkait langsung dengan EDC. Terutama karena masalah utama adalah karakterisasi pasangan non-lintas, dan juga karena ada topologi yang jauh lebih kuat daripada rasa geometris untuk pertanyaan ini (dan kami memiliki bukti mendalam bahwa EDC secara intrinsik geometris)

Suresh Venkat

Jumlah triangulasi seperangkat poin

Jawaban: