Garis Atas Amplop Dinamis dalam pesawat

8

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 .(x)x(x,)
Joe
sumber
6
Untuk garis, dualitas titik-garis harus menerjemahkan ini ke masalah tentang lambung cembung dinamis, yang dipelajari dengan baik.
seseorang
2
@ seseorang terima kasih atas komentar bermanfaat Anda! Mengikuti alur pemikiran itu dengan cepat membawa saya ke referensi berikut, yang membahas tumpukan parametrik, yang tampaknya merupakan struktur data yang saya cari. madalgo.au.dk/~gerth/papers/focs02.pdf
Joe
3
Lihat juga citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174 dan referensi di dalamnya.
Joe
1
@ Jo: Saya tidak yakin tentang etiket tetapi saya pikir Anda harus membuat jawaban dan menerimanya, untuk membantu pembaca masa depan dari pertanyaan ini.
Maks.

Jawaban:

5

"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 )HAI(catatan1+ϵn) HAI(catatann)

James King
sumber
1
Ups, sudahlah. Tampaknya Anda telah menemukan hasil yang lebih baru yang menurut saya mengalahkan ini.
James King
3

Struktur data yang saya cari disebut tumpukan parametrik . Yaitu, tumpukan di mana setiap kunci adalah fungsi linier (garis) dan bukan kunci tetap. The query(x)operasi yang dijelaskan di atas bersesuaian dengan find-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 memiliki find-min( ) permintaan, kami diizinkan untuk bertanya ( t 2 ) hanya jika t 2t 1 .t1find-mint2t2t1

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 )HAI(catatann)HAI(catatan2n)

Namun, kemudian ada beberapa perbaikan teoritis untuk hasil klasik. Di FOCS 99, kertas Chan

memberikan struktur data dengan waktu diamortisasi untuk pembaruan.HAI(catatan1+ϵn)

Kemudian, penulis berikut (secara mandiri) meningkatkan batas waktu menjadi untuk penghapusan dan untuk penyisipan.O ( log n log log log n )HAI(catatanncatatancatatann)HAI(catatanncatatancatatancatatann)

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 .HAI(catatann)

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 )Θ(catatann/catatancatatann)HAI(catatanncatatancatatann)HAI(catatan2n)

Joe
sumber
3
Oh Tidak. Semua hasil ini sangat rumit. Makalah asli Overmars / Van Leuven (lihat en.wikipedia.org/wiki/Dynamic_convex_hull ) masih merupakan permata dan dapat dengan mudah diimplementasikan. Log ^ 2 untuk beberapa operasi. Tapi ini kasus terburuk.
Sariel Har-Peled
1
Saya pikir tesis Riko Jacob memiliki versi lengkap buktinya? Tapi saya setuju dengan Sariel bahwa Anda harus tetap berpegang pada Overmars / Van Leuven
Suresh Venkat
@ SureshVenkat Mengapa saya harus tetap menggunakan Overmars / Van Leuven?
Joe
Saya kira itu tergantung pada apa yang Anda butuhkan untuk algoritma.
Suresh Venkat
Pada ram kata, kita bisa mendapatkan waktu permintaan yang lebih cepat: people.csail.mit.edu/mip/paper/dynhull/paper.pdf
Joe