×

zbMATH — the first resource for mathematics

Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os. (English) Zbl 1421.68029
Summary: We revisit the problem of constructing an external memory data structure on a planar subdivision formed by \(n\) segments to answer point location queries optimally in \(O(\log _B n)\) I/Os. The objective is to achieve the I/O cost of \(\operatorname{sort}(n) = O(\frac{n}{B} \log _{M/B} \frac{n}{B})\), where \(B\) is the number of words in a disk block, and \(M\) being the number of words in memory. The previous algorithms are able to achieve this either in expectation or under the tall cache assumption of \(M \ge B^2\). We present the first algorithm that solves the problem deterministically for all values of \(M\) and \(B\) satisfying \(M \ge 2B\).
MSC:
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achakeev, D.; Seeger, B., Efficient bulk updates on multiversion B-trees, PVLDB, 6, 1834-1845, (2013)
[2] Afshani, P.; Chan, TM, On approximate range counting and depth, Discrete Comput. Geom., 42, 3-21, (2009) · Zbl 1180.68124
[3] Agarwal, P.K., Arge, L.., Brodal, G.S.., Vitter, J.S.: I/O-efficient dynamic point location in monotone planar subdivisions. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11-20 (1999) · Zbl 0938.68144
[4] Aggarwal, A.; Vitter, JS, The input/output complexity of sorting and related problems, CACM, 31, 1116-1127, (1988)
[5] Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 305-314 (2006)
[6] Arge, L.; Brodal, GS; Rao, SS, External memory planar point location with logarithmic updates, Algorithmica, 63, 457-475, (2012) · Zbl 1267.68100
[7] Arge, L.; Danner, A.; Teh, S-M, I/O-efficient point location using persistent B-trees, ACM J. Exp. Algorithmics, 8, 1-2, (2003) · Zbl 1085.68565
[8] Arge, L.; Vahrenhold, J., I/O-efficient dynamic planar point location, Comput. Geom., 29, 147-162, (2004) · Zbl 1056.68062
[9] Arge, L.; Vengroff, DE; Vitter, JS, External-memory algorithms for processing line segments in geographic information systems, Algorithmica, 47, 1-25, (2007) · Zbl 1107.68118
[10] Aronov, B.; Har-Peled, S., On approximating the depth and related problems, SIAM J. Comput., 38, 899-921, (2008) · Zbl 1180.68278
[11] Baumgarten, H.; Jung, H.; Mehlhorn, K., Dynamic point location in general subdivisions, J. Algorithms, 17, 342-380, (1994) · Zbl 0820.68122
[12] Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 195-207 (2002) · Zbl 1056.68511
[13] Bentley, JL; Saxe, JB, Decomposable searching problems I: static-to-dynamic transformation, J. Algorithms, 1, 301-358, (1980) · Zbl 0461.68065
[14] Bertino, E., Catania, B., Shidlovsky, B.: Towards optimal indexing for segment databases. In: Proceedings of Extending Database Technology (EDBT), pp. 39-53 (1998) · Zbl 1337.68085
[15] Cheng, S-W; Janardan, R., New results on dynamic planar point location, SIAM J. Comput., 21, 972-999, (1992) · Zbl 0756.68092
[16] de Berg, M., Haverkort, H.J., Thite, S., Toma, L.: I/O-efficient map overlay and point location in low-density subdivisions. In: International Symposium on Algorithms and Computation (ISAAC), pp. 500-511 (2007) · Zbl 1193.68276
[17] den Bercken, J.V., Seeger, B., Widmayer, P.: A generic approach to bulk loading multidimensional index structures. In: Proceedings of Very Large Data Bases (VLDB), pp. 406-415 (1997)
[18] Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 714-723 (1993)
[19] Haussler, D.; Welzl, E., Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2, 127-151, (1987) · Zbl 0619.68056
[20] Maheshwari, A.; Zeh, N., I/O-efficient planar separators, SIAM J. Comput., 38, 767-801, (2008) · Zbl 1163.05053
[21] Overmars, M.H.: Range searching in a set of line segments. In: Proceedings of Symposium on Computational Geometry (SoCG), pp. 177-185 (1985)
[22] Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 232-240 (2006) · Zbl 1301.68150
[23] Sarnak, N.; Tarjan, RE, Planar point location using persistent search trees, CACM, 29, 669-679, (1986) · Zbl 0732.68102
[24] van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators and i/o-efficient algorithms for planar graphs. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 901-918 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.