Title
Stabbing horizontal segments with vertical rays
Abstract
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.
Year
DOI
Venue
2012
10.1145/2261250.2261298
Symposium on Computational Geometry 2013
Keywords
DocType
Citations 
amortized time,consuming space o,intersecting q,consumes o,reported segment,internal memory,n horizontal segment,logb n,external memory model,vertical ray,dynamic set,external memory,data structure
Conference
1
PageRank 
References 
Authors
0.35
13
1
Name
Order
Citations
PageRank
Yufei Tao17231316.71