External memory planar point location with logarithmic updates

ABSTRACT

Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log_B N) I/Os and queries can be answered in O(log_B² N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(log_B² N) I/Os, but only supports insertions in amortized O(log_B² N) I/Os. Our structure is also considerably simpler than previous structures.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Gerth Stølting Brodal , Jeffrey S. Vitter, I/O-efficient dynamic point location in monotone planar subdivisions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 17-19, 1999, Baltimore, Maryland, United States
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: Lars Arge , Gerth Stolting Brodal , Loukas Georgiadis, Improved Dynamic Planar Point Location, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.305-314, October 21-24, 2006 [doi>10.1109/FOCS.2006.40]
• 4: Lars Arge , Andrew Danner , Sha-Mayn Teh, I/O-efficient point location using persistent B-trees, Journal of Experimental Algorithmics (JEA), 8, 2003 [doi>10.1145/996546.996549]
• 5: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.685-694, January 25-27, 1998, San Francisco, California, United States
• 6: Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location, Computational Geometry: Theory and Applications, v.29 n.2, p.147-162, October 2004 [doi>10.1016/j.comgeo.2003.04.001]
• 7: Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems, Algorithmica, v.47 n.1, p.1-25, January 2007 [doi>10.1007/s00453-006-1208-z]
• 8: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 9: Hanna Baumgarten , Hermann Jung , Kurt Mehlhorn, Dynamic point location in general subdivisions, Journal of Algorithms, v.17 n.3, p.342-380, Nov. 1994
• 10: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.
• 11: Siu Wing Cheng , Ravi Janardan, New results on dynamic planar point location, SIAM Journal on Computing, v.21 n.5, p.972-999, Oct. 1992 [doi>10.1137/0221057]
• 12: Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps, SIAM Journal on Computing, v.25 n.1, p.207-233, Feb. 1996 [doi>10.1137/S0097539792224516]
• 13: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 14: A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276914]
• 15: H. Edelsbrunner. A new approach to rectangle intersections, Part I. Internat. J. Comput. Math., 13:209--219, 1983.
• 16: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 17: H. Edelsbrunner and H. A. Maurer. A space-optimal solution of general region location. Theoretical Computer Science, 16:329--336, 1981.
• 18: M. T. Goodrich , Jyh-Jong Tsay , D. E. Vengroff , J. S. Vitter, External-memory computational geometry, Proceedings of the Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, p.714-723, November 03-05, 1993 [doi>10.1109/SFCS.1993.366816]
• 19: S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157--184, 1982.
• 20: D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28--35, 1983.
• 21: Mark H. Overmars, Range searching in a set of line segments, Proceedings of the first annual symposium on Computational geometry, p.177-185, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323257]
• 22: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 23: Jan Vahrenhold , Klaus Hinrichs, Planar Point Location for Large Data Sets: To Seek or Not to Seek, Proceedings of the 4th International Workshop on Algorithm Engineering, p.183-194, September 05-08, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design

Keywords:
dynamic data structure, external memory, planar subdivisions, point location