Ada algoritma yang mudah untuk menghitung amplop atas dari susunan garis di pesawat. Lihat misalnya bagian 2.3 dalam survei, urutan Davenport-Schinzel dan aplikasi geometriknya .
Adakah algoritma / struktur data yang diketahui untuk versi dinamis dari masalah yang sama? Artinya, kami ingin mempertahankan amplop atas dari serangkaian garis di pesawat di bawah operasi berikut:
- insert ): menambahkan baris ke setℓ
- delete : menghapus baris dari set
- query : mengembalikan garis dengan koordinat di amplop atas. Dengan kata lain, kembalikan garis dalam himpunan yang pertama kali dipukul oleh sinar ke bawah vertikal dari titik .
Jawaban:
"seseorang" benar. Makalah Timothy Chan "Dynamic Planar Convex Hull Operations di Near-Logarithmic Amortized Time" muncul untuk menyelesaikan masalah dengan penyisipan / penghapusan mengambil waktu diamortisasi , dan kueri mengambil waktu. Dia memecahkan masalah Anda yang merupakan masalah ganda untuk cembung lambung.O ( log n )O ( log1 + ϵn ) O ( logn )
sumber
Struktur data yang saya cari disebut tumpukan parametrik . Yaitu, tumpukan di mana setiap kunci adalah fungsi linier (garis) dan bukan kunci tetap. Thet1 t2 t2≥ t1
query(x)
operasi yang dijelaskan di atas bersesuaian denganfind-min(x)
operasi dalam tumpukan parametrik. Ada struktur data terkait, yang disebut tumpukan kinetik , yang merupakan tumpukan parametrik di mana parameter, waktu, hanya bergerak maju. Dengan kata lain, setelah kami memilikifind-min
( ) permintaan, kami diizinkan untuk bertanya ( t 2 ) hanya jika t 2 ≥ t 1 .find-min
Seperti yang diamati oleh "seseorang", masalah tumpukan parametrik dapat direduksi menjadi hull planar dinamis melalui dualitas titik-garis.
Sebagian besar makalah yang memecahkan masalah ini menggunakan struktur data "penghapusan hanya" semi-dinamis, dan kemudian menggunakan teknik dinamika Bentley dan Saxe untuk mengubah struktur data mereka untuk juga mendukung penyisipan. ( JL Bentley dan JB Saxe, masalah pencarian terurai I:. Static-to-dinamis transformasi ) Lihat juga J catatan kuliah FFE iniϵ untuk gambaran tentang bagaimana jenis karya transformasi.
Hasil klasik di daerah ini adalah karena Overmars dan van Leeuwen, Pemeliharaan konfigurasi di pesawat , yang mencapai waktu query dan (kasus terburuk) waktu update. Jika kami ingin menerapkan solusi untuk masalah ini, ini adalah versi untuk digunakan.O ( log 2 n )O ( logn ) O ( log2n )
Namun, kemudian ada beberapa perbaikan teoritis untuk hasil klasik. Di FOCS 99, kertas Chan
memberikan struktur data dengan waktu diamortisasi untuk pembaruan.O ( log1 + ϵn )
Kemudian, penulis berikut (secara mandiri) meningkatkan batas waktu menjadi untuk penghapusan dan untuk penyisipan.O ( log n log log log n )O ( logn logcatatann ) O ( logn logcatatancatatann )
Kaplan, Tarjan, dan Tsioutsiouliklis Tumpukan Kinetic Lebih Cepat dan Penggunaannya dalam Penjadwalan Siaran di SODA 2001
Semua kutipan di atas mendukungO ( logn )
find-min
kueri dalam waktu .Baru-baru ini, Brodal dan Jacob telah semakin meningkatkan hasilnya untuk mendukung pembaruan dalam waktu diamortisasi . Hasilnya cukup rumit, dan saya hanya dapat menemukan versi lengkap dari makalah mereka dalam bentuk draft , namun hasilnya juga dirinci dalam Ph.D. Disertasi .O ( logn )
Baru-baru ini, Chan memberikan hasil lain yang terkait dengan kueri cangkang planar dinamis, termasuk "Struktur data yang sepenuhnya dinamis untuk mempertahankan satu set n poin di pesawat sehingga kita dapat menemukan tepi lambung cembung memotong garis kueri".
Pada RAM kata, Demaine dan Pătraşcu menunjukkan bahwa waktu kueri optimal adalah , dan tergantung pada jenis kueri (nol atau satu dimensi vs dua dimensi), berikan waktu pembaruan dari atau .O ( log n log log n ) O ( log 2 n )Θ ( logn / logcatatann ) O ( logn logcatatann ) O ( log2n )
sumber