Using persistent data structures for adding range restrictions to searching problems
Lenhof, Hans-Peter ; Smid, Michiel
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 25-49 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_1_25_0,
     author = {Lenhof, Hans-Peter and Smid, Michiel},
     title = {Using persistent data structures for adding range restrictions to searching problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {25-49},
     mrnumber = {1271125},
     zbl = {0998.68520},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_1_25_0}
}

Lenhof, Hans-Peter; Smid, Michiel. Using persistent data structures for adding range restrictions to searching problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 25-49. http://gdmltest.u-ga.fr/item/ITA_1994__28_1_25_0/

1. J. L. Bentley, Decomposable Searching Problems, Inform. Proc. Lett., 1979, 8, 244-251. | MR 534072 | Zbl 0404.68067

2. J. L. Bentley, Multidimensional Divide and Conquer, Comm. ACM., 1980, 23, 214-229. | MR 567150 | Zbl 0434.68049

3. B. Chazelle and L. J. Guibas, Fractional Cascading I: a Data Structuring Technique, Algorithmica, 1986, 1, 133-162. | MR 858402 | Zbl 0639.68056

4. P. F. Dietz and R. Raman, Persistence, Amortization and Randomization, Tech. Report 353, University of Rochester, 1991. | MR 1095822

5. M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyerauf Der Heide, H. Rohnert, R. E. Tarjan, Dynamic Perfect Hashing, Proc. 29-th Annual IEEE Symp. on Foundations of Computer Science, 1988, 524-531.

6. J. R. Driscoll, N. Sarnak, D. D. Sleator and R. E. Tarjan, Making Data Structures Persistent, J. Comput. System Sci., 1989, 38, 86-124. | MR 990051 | Zbl 0667.68026

7. H. Edelsbrunner, A Note on Dynamic Range Searching, Bull. of the EATCS, 1981, 15, 34-40.

8. H. N. Gabow, J. L. Bentley and R. E. Tarjan, Scaling and Related Techniques for Geometry Problems, Proc. 16-th Annual ACM Symp. on Theory of Computing, 1984, 135-143.

9. R. Klein, O. Nurmi, T. Ottmann and D. Wood, A Dynamic Fixed Windowing Problem, Algorithmica, 1989, 4, 535-550. | MR 1019392 | Zbl 0684.68035

10. K. Mehlhorn and S. Näher, Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space, Inform. Proc. Lett., 1990, 35, 183-189. | MR 1066121 | Zbl 0702.68042

11. M. H. Overmars, The Design of Dynamic Data Structures, Lecture Notes in Computer Science, 1983, Vol. 156, Springer-Verlag, Berlin. | MR 710832 | Zbl 0545.68009

12. M. H. Overmars, Efficient Data Structures for Range Searching on a Grid, J. of Algorithms, 1988, 9, 254-275. | MR 936109 | Zbl 0637.68067

13. N. Sarnak and R. E. Tarjan, Planar Point Location Using Persistent Search Trees, Comm. A.C.M., 1986, 29, 669-679. | MR 848411

14. H. W. Scholten and M. H. Overmars, General Methods for Adding Range Restrictions to Decomposable Searching Problems, J. Symbolic Computation, 1989, 7, 1-10. | MR 984267 | Zbl 0668.68073

15. P. Van Emde Boas, Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inform. Proc. Lett., 1977, 6, 80-82. | Zbl 0364.68053

16. P. Van Emde Boas, R. Kaas and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Math. Systems Theory, 1977, 10, 99-127. | MR 431777 | Zbl 0363.60104

17. D. E. Willard and G. S. Lueker, Adding Range Restriction Capability to Dynamic Data Structures, J. A.C.M., 1985, 32, 597-617. | MR 796204 | Zbl 0629.68097