Abstract
We consider the problem of maintaining dynamically a set of points in the plane and supporting range queries of the type [a,b]×( − ∞ , c]. We assume that the inserted points have their x-coordinates drawn from a class of smooth distributions, whereas the y-coordinates are arbitrarily distributed. The points to be deleted are selected uniformly at random among the inserted points. For the RAM model, we present a linear space data structure that supports queries in O(loglogn + t) expected time with high probability and updates in O(loglogn) expected amortized time, where n is the number of points stored and t is the size of the output of the query. For the I/O model we support queries in O(loglog B n + t/B) expected I/Os with high probability and updates in O(log B logn) expected amortized I/Os using linear space, where B is the disk block size. The data structures are deterministic and the expectation is with respect to the input distribution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P., Erickson, J.: Geometric range rearching and its relatives. In: Chazelle, B., Goodman, J., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, pp. 1–56. American Mathematical Society Press (1999)
Kanellakis, P.C., Ramaswamy, S., Vengroff, D.E., Vitter, J.S.: Indexing for data models with constraints and classes. In: Proc. ACM SIGACT-SIGMOD-SIGART PODS, pp. 233–243 (1993)
McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257–276 (1985)
Willard, D.E.: Examining computational geometry, van emde boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030–1049 (2000)
Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proc. ACM SIGMOD-SIGACT-SIGART PODS, pp. 346–357 (1999)
Andersson, A., Mattsson, C.: Dynamic interpolation search in o(log log n) time. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol. 700, pp. 15–27. Springer, Heidelberg (1993)
Kaporis, A., Makris, C., Sioutas, S., Tsakalidis, A., Tsichlas, K., Zaroliagis, C.: Improved bounds for finger search on a RAM. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 325–336. Springer, Heidelberg (2003)
Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proc. IEEE FOCS, pp. 135–141 (1996)
Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. ACM-SIAM SODA, pp. 550–555 (1998)
Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 54(3), 13 (2007)
Arge, L., Vitter, J.S.: Optimal dynamic interval management in external memory (extended abstract). In: Proc. IEEE FOCS, pp. 560–569 (1996)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)
Mehlhorn, K., Tsakalidis, A.: Dynamic interpolation search. J. ACM 40(3), 621–634 (1993)
Kaporis, A., Makris, C., Sioutas, S., Tsakalidis, A., Tsichlas, K., Zaroliagis, C.: Dynamic interpolation search revisited. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 382–394. Springer, Heidelberg (2006)
Kaporis, A.C., Makris, C., Mavritsakis, G., Sioutas, S., Tsakalidis, A.K., Tsichlas, K., Zaroliagis, C.D.: ISB-tree: A new indexing scheme with efficient expected behaviour. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 318–327. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodal, G.S., Kaporis, A.C., Sioutas, S., Tsakalidis, K., Tsichlas, K. (2009). Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)