Optimal dynamic vertical ray shooting in rectilinear planar subdivisions

ABSTRACT

In this paper we consider the dynamic vertical ray shooting problem, that is the task of maintaining a dynamic set S of n non intersecting horizontal line segments in the plane subject to 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 deletions in O(log n) worst-case time. Our structure works in the comparison model and uses a RAM.

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: 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]
• 3: 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]
• 4: Hanna Baumgarten , Hermann Jung , Kurt Mehlhorn, Dynamic point location in general subdivisions, Journal of Algorithms, v.17 n.3, p.342-380, Nov. 1994
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Y. J. Chiang and R. Tamassia. Dynamization of the trapezoid method for planar point location in monotone subdivisions. International Journal of Computational Geometry and Applications., 2(3):311--333, 1992.
• 10: 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
• 11: 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
• 12: 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]
• 13: Y. Giyora. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. Master's thesis, Dept. of Computer Science, Tel-Aviv University, ISRAEL, 2006.
• 14: 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]
• 15: 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]
• 16: K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215--241, 1990.
• 17: 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
• 18: 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]
• 19: 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
• 20: Rajeev Raman, Eliminating amortization: on data structures with guaranteed response time, University of Rochester, Rochester, NY, 1993
• 21: P. van Emde Boas. Preserving order in a forest in less than logarithmic time. Information Processing Letters, 6(3):80--82, 1977.
• 22: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99--127, 1977.
• 23: 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]