
doi: 10.1145/2559153
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.
Dynamic data structures, 2601 Mathematics (miscellaneous), Ray stabbing, Segment intersection, Computational geometry, Pointer machines
Dynamic data structures, 2601 Mathematics (miscellaneous), Ray stabbing, Segment intersection, Computational geometry, Pointer machines
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
