Dynamic Ray Stabbing
Yufei Tao · ACM Transactions on Algorithms · 2014
We consider maintaining a dynamic set S of N horizontal segments in ℝ 2 such that, given a vertical ray Q in ℝ 2 , the segments in S intersecting Q can be reported efficiently. In the external memory model, we give a structure that consumes O ( N / B ) space, answers a query in O (log B N + K / B ) time (where K is the number of reported segments), and can be updated in O (log B N ) amortized time per insertion and deletion. With B set to a constant, the structure also works in internal memory, consuming space O ( N ), answering a query in O (log N + K ) time, and supporting an update in O (log N ) amortized time.