(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
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.
Eric Price, David P. Woodruff
FOCS 2011
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization