39 citations · 40 across the 4 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
cs.DS2005★ 39 cited
On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching i…
cs.DS2005
Logarithmic Lower Bounds in the Cell-Probe Model
Mihai Patrascu, Erik D. Demaine
We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per op…