Cakupan Rectangle oleh Sweep Line

Sayangnya saya diberi latihan, tetapi saya tidak berhasil.

Ada satu set persegi panjang $R_{1}..R_{n}$ dan persegi panjang $R_{0}$ . Menggunakan algoritma plane sweeping menentukan apakah sepenuhnya dicakup oleh set .$R_{0}$$R_{1}..R_{n}$

Untuk detail lebih lanjut tentang prinsip algoritma garis sapu lihat di sini .

Mari kita mulai dari awal. Awalnya kita tahu algoritma garis sapu sebagai algoritma untuk menemukan persimpangan segmen garis yang membutuhkan dua struktur data:

• set titik acara (ini menyimpan titik akhir segmen dan titik persimpangan)$Q$
• status (struktur dinamis untuk himpunan segmen yang memotong garis sweep)$T$

Gagasan Umum: asumsikan bahwa garis sapuan adalah garis vertikal yang mulai mendekati himpunan segi empat dari kiri. Urutkan semua koordinat persegi panjang dan simpan dalam dalam urutan yang meningkat - harus mengambil . Mulai dari titik kejadian pertama, untuk setiap titik tentukan himpunan persegi panjang yang berpotongan pada koordinat diberikan , identifikasi segmen kontinu persegi panjang persimpangan dan periksa apakah mereka mencakup R 0 sepenuhnya pada koordinat x saat ini . Dengan T sebagai pohon biner, ia akan mengambil O ( log n ) . Jika ada bagian darix Q O ( n log n ) $l$$x$$Q$$O(n\log n)$$x$$R_{0}$$x$$T$$O(\log n)$ tetap terbuka bahwa R 0 tidak sepenuhnya tertutup.$R_{0}$$R_{0}$

Detail: Gagasan algoritme persimpangan segmen adalah bahwa hanya segmen bersebelahan yang bersinggungan. Berdasarkan fakta ini kami membangun status dan mempertahankannya di seluruh algoritma. Saya mencoba untuk menemukan ide yang sama dalam kasus ini dan sejauh ini tidak berhasil, satu-satunya hal yang dapat saya katakan adalah dua persegi panjang berpotongan jika koordinat x dan y yang sesuai tumpang tindih.$T$$x$$y$

Masalahnya adalah bagaimana membangun dan memelihara , dan apa kompleksitas bangunan dan mempertahankan T adalah. Saya berasumsi bahwa pohon R dapat sangat berguna dalam kasus ini, tetapi ketika saya menemukan itu sangat sulit untuk menentukan persegi panjang batas minimum menggunakan pohon R.$T$$T$

Apakah Anda punya ide tentang cara mengatasi masalah ini, dan khususnya cara membangun ?$T$

Mari kita mulai dengan persegi panjang yang disejajarkan dengan sumbu, karena ada semacam argumen langsung yang mudah. Kami akan menyapu garis vertikal. Peristiwa adalah titik akhir dari tepi horizontal dari persegi panjang. Saat kita menyapu, kita mempertahankan satu set interval pada garis sapuan yang "terbuka" oleh R i , i ≥ 1 :$n$$R_i$$i\ge 1$

• Tambahkan interval vertikal yang dicakup oleh persegi panjang ke garis sapuan ketika kita pertama kali bertemu R $R_i$$R_i$
• Hapus interval vertikal yang tercakup oleh persegi panjang dari garis sapuan ketika bergerak melewati R $R_i$$R_i$

Sangat mudah untuk melakukan ini dengan pohon biner sehingga pembaruan membutuhkan waktu . (Masalahnya adalah, pada dasarnya, 1-dimensi. Anda mengetahui apakah titik akhir berada dalam interval terbuka dan memperluas / menggabungkan secara tepat saat menambahkan dan memperpanjangnya saat melepas.)$O(\log n)$

Kemudian Anda hanya memeriksa bahwa, dalam rentang , tidak ada interval yang tidak ditemukan yang pernah memotong rentang vertikal R 0 . Semuanya adalah O ( n log n ) waktu O ( n ) ruang.$R_0$$R_0$$O(n\log n)$$O(n)$

Untuk kasus umum, trik yang jelas tidak begitu cepat. Gunakan algoritma garis sapuan standar untuk menghitung seluruh subdivisi planar yang disebabkan oleh persegi panjang.

Jelas beberapa himpunan seperti cakram dari muka meliputi R 0 . Dengan sendirinya, ini tidak cukup memberi tahu kami, karena yang kami minati adalah apakah ada dari wajah-wajah ini di dalam R 0 dan di luar persegi panjang lainnya. Untuk melakukan ini, kami memodifikasi konstruksi sedikit, sehingga ketika kami menambahkan tepi, kami menandai satu sisi dengan identitas persegi panjang yang ada di dalamnya. Ini menambahkan O ( 1 ) overhead, sehingga konstruksinya adalah O ( n 2 log n ) waktu; tanpa asumsi pada persegi panjang, output bisa Ω ( n 2$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$ dalam ukuran, jadi kami menggunakan banyak ruang dalam kasus terburuk, jadi waktunya adalah, "optimal secara eksistensial" meskipun tidak "peka keluaran".

Akhirnya, ditutupi selama tidak ada satu pun wajah di F ′ yang hanya memiliki tepi yang tidak ditandai sebagai salah satu dari R i . Intinya adalah bahwa jika tepi f ada di R i , maka seluruh f juga. Bayangkan menyapu garis lebih f ortogonal sepanjang tepi ini: hanya dapat meninggalkan R i baik di luar dari f atau f dibatasi oleh lebih dari satu tepi R i .$R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

Jadi kesimpulannya adalah bahwa kasus khusus adalah dan yang umum adalah O ( n 2 log n ) setidaknya, tetapi saya curiga ini dapat diperbaiki.$O(n\log n)$$O(n^2\log n)$