×

zbMATH — the first resource for mathematics

I/O-efficient dynamic planar point location. (English) Zbl 1056.68062
Summary: We present an I/O-efficient dynamic data structure for point location in a general planar subdivision. Our structure uses \(O(N/B)\) disk blocks of size \(B\) to store a subdivision of size \(N\). Queries can be answered in \(O(\log^2_BN)\) I/Os in the worst case, and insertions and deletions can be performed in \(O(\log^2_BN)\) and \(O(\log_BN)\) I/Os amortized, respectively.
Part of our data structure is based on an external version of the so-called logarithmic method that allows for efficient dynamization of static external-memory data structures with certain characteristics. Another important part of our structure is an external data structure for vertical ray-shooting among line segments in the plane with endpoints on \(\sqrt B+1\) vertical lines, developed using an external version of dynamic fractional cascading. We believe that these methods could prove helpful in the development of other dynamic external memory data structures.

MSC:
68P05 Data structures
PDF BibTeX Cite
Full Text: DOI
References:
[1] Agarwal, P.K.; Arge, L.; Brodal, G.S.; Vitter, J.S., I/O-efficient dynamic point location in monotone planar subdivisions, (), 11-20 · Zbl 0938.68144
[2] Aggarwal, A.; Vitter, J.S., The input/output complexity of sorting and related problems, Comm. ACM, 31, 9, 1116-1127, (1988)
[3] Arge, L., External memory data structures, (), 313-358 · Zbl 1010.68039
[4] Arge, L.; Danner, A.; Teh, S.-M., I/O-efficient point location using persistent B-trees, () · Zbl 1085.68565
[5] Arge, L.; Procopiuc, O.; Ramaswamy, S.; Suel, T.; Vitter, J.S., Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems, (), 685-694 · Zbl 0930.68048
[6] Arge, L.; Vengroff, D.E.; Vitter, J.S., External-memory algorithms for processing line segments in geographic information systems, (), 295-310, To appear in special issues of Algorithmica on Geographical Information Systems
[7] Arge, L.; Vitter, J.S., Optimal external memory interval management, SIAM J. comput., 32, 6, 1488-1508, (2003) · Zbl 1030.68027
[8] Baumgarten, H.; Jung, H.; Mehlhorn, K., Dynamic point location in general subdivisions, J. algorithms, 17, 2, 342-380, (1994) · Zbl 0820.68122
[9] Bayer, R.; McCreight, E., Organization and maintenance of large ordered indexes, Acta inform., 1, 173-189, (1972) · Zbl 0226.68008
[10] Bentley, J.L., Decomposable searching problems, Inform. process. lett., 8, 5, 244-251, (1979) · Zbl 0404.68067
[11] Chazelle, B.; Guibas, L.J., Fractional cascading: I. A data structuring technique, Algorithmica, 1, 2, 133-162, (1986) · Zbl 0639.68056
[12] Cheng, S.W.; Janardan, R., New results on dynamic planar point location, SIAM J. comput., 21, 5, 972-999, (1992) · Zbl 0756.68092
[13] Chiang, Y.-J.; Preparata, F.P.; Tamassia, R., A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, SIAM J. comput., 25, 1, 207-233, (1996) · Zbl 0841.68120
[14] Comer, D., The ubiquitous B-tree, ACM comput. surv., 11, 2, 121-137, (1979) · Zbl 0419.68034
[15] Crauser, A.; Ferragina, P.; Mehlhorn, K.; Meyer, U.; Ramos, E., Randomized external-memory algorithms for some geometric problems, Internat. J. comput. geom. appl., 11, 3, 305-337, (2001) · Zbl 1074.68669
[16] Edelsbrunner, H., A new approach to rectangle intersections, part I, Internat. J. comput. math., 13, 209-219, (1983) · Zbl 0513.68058
[17] Edelsbrunner, H.; Guibas, L.J.; Stolfi, J., Optimal point location in a monotone subdivision, SIAM J. comput., 15, 2, 317-340, (1986) · Zbl 0602.68102
[18] Edelsbrunner, H.; Maurer, H.A., A space-optimal solution of general region location, Theoret. comput. sci., 16, 329-336, (1981) · Zbl 0468.68075
[19] Goodrich, M.T.; Tsay, J.-J.; Vengroff, D.E.; Vitter, J.S., External-memory computational geometry, (), 714-723
[20] Huddleston, S.; Mehlhorn, K., A new data structure for representing sorted lists, Acta inform., 17, 157-184, (1982) · Zbl 0481.68061
[21] Kirkpatrick, D.G., Optimal search in planar subdivisions, SIAM J. comput., 12, 1, 28-35, (1983) · Zbl 0501.68034
[22] Mehlhorn, K.; Näher, S., Dynamic fractional cascading, Algorithmica, 5, 215-241, (1990) · Zbl 0693.68038
[23] Overmars, M.H., The design of dynamic data structures, Lecture notes in comput. sci., vol. 156, (1983), Springer Berlin · Zbl 0545.68009
[24] Overmars, M.H., Range searching in a set of line segments, (), 177-185
[25] Sarnak, N.; Tarjan, R.E., Planar point location using persistent search trees, Comm. ACM, 29, 7, 669-679, (1986)
[26] Snoeyink, J., Point location, (), 559-574 · Zbl 0907.68196
[27] Tamassia, R.; Preparata, F.P., Dynamic maintenance of planar digraphs, with applications, Algorithmica, 5, 509-527, (1990) · Zbl 0697.68026
[28] Vahrenhold, J.; Hinrichs, K.H., Planar point location for large data sets: to seek or not to seek, ACM J. of exp. alg., 7, (August 2002), Article 8, 21 pp
[29] Vitter, J.S., External memory algorithms and data structures: dealing with MASSIVE data, ACM comput. surv., 33, 2, 209-271, (2001)
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.