Two general methods for dynamizing decomposable searching problems
作者： M. H. Overmars , J. van Leeuwen
DOI: 10.1007/BF02241781
关键词:
摘要: We define two classes of decomposable searching problems and consider ways efficiently dynamizing them. For the first class, DD, we show that both insertions deletions can be processed efficiently. second MD, exploit a merge technique to obtain better insertion times. also give number examples which methods apply, including dynamic maintenance quadtrees common intersection finitely many halfspaces in plane.
springer.com
sci-hub.se 参考文章(7)
Dan E Willard, Balanced Forests of K-D* Trees as a Dynamic Data Structure. ,(1978)
James B. Saxe, Jon Louis Bentley, Transforming static data structures to dynamic structures 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). pp. 148- 168 ,(1979) , 10.1109/SFCS.1979.47
R. A. Finkel, J. L. Bentley, Quad trees a data structure for retrieval on composite keys Acta Informatica. ,vol. 4, pp. 1- 9 ,(1974) , 10.1007/BF00288933
Jon Louis Bentley, Decomposable searching problems Information Processing Letters. ,vol. 8, pp. 244- 251 ,(1979) , 10.1016/0020-0190(79)90117-0
Mark H. Overmars, Jan van Leeuwen, Maintenance of configurations in the plane Journal of Computer and System Sciences. ,vol. 23, pp. 166- 204 ,(1981) , 10.1016/0022-0000(81)90012-X
Jan Van Leeuwen, Derick Wood, Dynamization of decomposable searching problems Information Processing Letters. ,vol. 10, pp. 51- 56 ,(1980) , 10.1016/S0020-0190(80)90073-3
Jon Louis Bentley, Multidimensional binary search trees used for associative searching Communications of the ACM. ,vol. 18, pp. 509- 517 ,(1975) , 10.1145/361002.361007