Stabbing Horizontal Segments with Vertical Rays

摘要

We consider maintaining a dynamic set S of N horizontal segments in R~2 such that, given a vertical ray Q in R~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 TV) 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.