Stabbing horizontal segments with vertical rays
Yufei Tao · 2012
We consider maintaining a dynamic set S of N horizontal segments in R2 such that, given a vertical ray Q in R2, 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(logB N + K/B) time (where K is the number of reported segments), and can be updated in O(logB 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.