Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
Yoav Giora, Haim Y. Kaplan · ACM Transactions on Algorithms · 2009
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.