Belajar segitiga di pesawat

Saya ditugaskan siswa saya masalah menemukan sebuah segitiga yang konsisten dengan koleksi poin di R 2 , diberi label dengan ± 1 . (A segitiga T adalah konsisten dengan sampel berlabel jika T berisi semua positif dan tidak ada poin negatif, oleh asumsi, mengakui sampel minimal 1 segitiga konsisten).$m$$\mathbb{R}^2$$\pm1$$T$$T$

Yang terbaik yang mereka (atau saya) bisa lakukan adalah algoritma yang berjalan dalam waktu , di mana m adalah ukuran sampel. Adakah yang bisa berbuat lebih baik?$O(m^6)$$m$

Seperti @TsuyoshiIto sarankan, ada algoritma -waktu untuk masalah ini, karena Edelsbrunner dan Preparata. Bahkan, algoritma mereka menemukan poligon cembung dengan jumlah tepi minimum yang memungkinkan yang memisahkan dua set titik. Mereka juga membuktikan Ω ( n log n ) batas bawah untuk masalah yang lebih umum dalam model pohon keputusan aljabar; Namun, tidak jelas apakah batas bawah ini berlaku untuk kasus segitiga.$O(n\log n)$$\Omega(n\log n)$

Penjelasan lengkap tentang algoritme terlalu panjang untuk dikirim di sini, tetapi inilah ide dasarnya. Biarkan menjadi cembung lambung dari poin positif. Untuk setiap titik negatif q , mempertimbangkan garis melalui q yang bersinggungan dengan C . Garis-garis ini membagi pesawat menjadi empat irisan, salah satunya berisi $C$$q$$q$$C$$C$ ; biarkan menjadi irisan berlawanan salah satu yang berisi C . Akhirnya, misalkan F ("wilayah terlarang") menjadi penyatuan semua irisan W ( q ) . Segitiga pemisah harus memisahkan C dari $W(q)$$C$$F$$W(q)$$C$$F$. Baik dan F dapat dibangun dalam waktu O ( n log n ) .$C$$F$$O(n\log n)$

Beri label pada tepi searah jarum jam dan berlawanan arah jarum jam. Edelsbrunner dan Preparata lanjut membuktikan bahwa jika sebuah segitiga memisahkan ada, maka ada segitiga yang memisahkan yang ujung-ujungnya adalah collinear dengan tepi searah jarum jam dari F . Dalam O ( n ) waktu tambahan, kita dapat menemukan tepi (harus searah jarum jam) dari F yang pertama kali terkena sinar dari setiap tepi searah jarum jam e ; sebut tepi ini sebagai "penerus" dari e . Pointer penerus membagi tepi searah jarum jam menjadi siklus; jika ada segitiga pemisah, salah satu siklus penerus ini memiliki panjang 3 (dan tidak ada yang memiliki panjang lebih dari 4).$F$$F$$O(n)$$F$$e$$e$

Lihat kertas asli untuk lebih jelasnya:

• Herbert Edelsbrunner dan Franco P. Preparata. Pemisahan poligon minimum . Informasi dan Komputasi 77 (3): 218–232, 1988.

Bagi saya tampaknya cukup untuk mempertimbangkan garis singgung dari titik '-1' ke cembung lambung poin '+1' sebagai kandidat untuk sisi (katakanlah bahwa '+1' poin akan menjadi bagian dalam ke T ).$T$$T$

Sayang sekali, saya tidak bisa menerbitkan gambar di sini. Tapi bayangkan ini: adalah garis singgung ke cembung cembung yang melewati beberapa titik '-1'. A adalah titik singgung. $t$$A$$B$ adalah titik ekstrim (lihat di bawah) pada , dan B C adalah garis singgung dari titik B ( C adalah titik singgung).$t$$BC$$B$$C$

Jadi, algoritmanya adalah sebagai berikut. Untuk setiap baris dari garis singgung kita dapat mencoba membangun segitiga berdasarkan itu:$t$

1. Hitung titik persimpangan dengan semua garis lainnya;$t$
2. Temukan ekstrim (terjauh dari ) titik B dan garis yang sesuai t ′ ke kanan (atau kiri) dari A , sedemikian rupa sehingga psuedotriangle A B C (= A B , B C dan bagian lambung cembung antara A dan C ) tidak mengandung poin '-1' (yaitu tidak mengandung poin apa pun).$A$$B$$t'$$A$$ABC$$AB$$BC$$A$$C$
3. Lakukan hal yang sama dengan garis dan lihat apakah kita dapat 'menutup' segitiga.$t'$

Sepertinya ini akan menjadi waktu berjalan. Mungkin ini bisa diperbaiki dengan menggunakan beberapa struktur data?$O(m^2)$