Optimal dynamic vertical ray shooting in rectilinear planar subdivisions

ABSTRACT

We consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set S of n nonintersecting horizontal line segments in the plane under a query that reports the first segment in S intersecting a vertical ray from a query point. We develop a linear-size structure that supports queries, insertions, and deletion in O(log n) worst-case time. Our structure works in the comparison model on a random access machine.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Ke Yi, An optimal dynamic interval stabbing-max data structure?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 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 , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 5: Hanna Baumgarten , Hermann Jung , Kurt Mehlhorn, Dynamic point location in general subdivisions, Journal of Algorithms, v.17 n.3, p.342-380, Nov. 1994
• 6: Amir M. Ben-Amram, What is a “pointer machine”?, ACM SIGACT News, v.26 n.2, p.88-95, June 1995 [doi>10.1145/202840.202846]
• 7: Guy E. Blelloch, Space-efficient dynamic orthogonal point location, segment intersection, and range reporting, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.894-903, January 20-22, 2008, San Francisco, California
• 8: Adam L. Buchsbaum , Michael T. Goodrich, Three-Dimensional Layers of Maxima, Algorithmica, v.39 n.4, p.275-286, May 2004 [doi>10.1007/s00453-004-1082-5]
• 9: Chan, T., and Pǎtraşcu, M. Transdichotomous results in computational geometry, I: Point location in sublogarithmic time. SIAM J. Comput.
• 10: Timothy M. Chan, Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.333-344, October 21-24, 2006 [doi>10.1109/FOCS.2006.62]
• 11: Chazelle, B., and Guibas, L. 1986. Fractional cascading: I. A data structuring technique. Algorithmica 1, 2, 133--162.
• 12: 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]
• 13: 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]
• 14: Chiang, Y. J., and Tamassia, R. 1992. Dynamization of the trapezoid method for planar point location in monotone subdivisions. Int. J. Comput. Geom. Appl. 2, 3, 311--333.
• 15: Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: Paul F. Dietz , Rajeev Raman, Persistence, amortization and randomization, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.78-88, January 28-30, 1991, San Francisco, California, United States
• 17: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 18: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 19: Yoav Giyora , Haim Kaplan, Optimal dynamic vertical ray shooting in rectilinear planar subdivisions, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.19-28, January 07-09, 2007, New Orleans, Louisiana
• 20: Michael T. Goodrich , Roberto Tamassia, Dynamic Trees and Dynamic Point Location, SIAM Journal on Computing, v.28 n.2, p.612-636, April 1999 [doi>10.1137/S0097539793254376]
• 21: Haim Kaplan , Eyal Molad , Robert E. Tarjan, Dynamic rectangular intersection with priorities, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780635]
• 22: Mehlhorn, K. 1986. Datenstrukturen und Algorithmen 1. Teubner.
• 23: Mehlhorn, K., and Näher, S. 1990. Dynamic fractional cascading. Algorithmica 5, 215--241.
• 24: Christian Worm Mortensen, Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 25: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 26: Mihai Patrascu, Planar Point Location in Sublogarithmic Time, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.325-332, October 21-24, 2006 [doi>10.1109/FOCS.2006.61]
• 27: Franco P. Preparata , Roberto Tamassia, Dynamic planar point location with optimal query time, Theoretical Computer Science, v.74 n.1, p.95-114, July 30, 1990
• 28: Rajeev Raman, Eliminating amortization: on data structures with guaranteed response time, University of Rochester, Rochester, NY, 1993
• 29: van Emde Boas, P. 1977. Preserving order in a forest in less than logarithmic time. Inf. Process. Lett. 6, 3, 80--82.
• 30: van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99--127.
• 31: Dan E. Willard, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Information and Computation, v.97 n.2, p.150-204, April 1992 [doi>10.1016/0890-5401(92)90034-D]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms

Keywords:
Ray shooting, planar point location