Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log2 n) space requirements and O(log3 n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(log N + t) query time, O(n log2 N) space and O(log2 N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique. © 1985.
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Eric Price, David P. Woodruff
FOCS 2011
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007