206 citations · 961 across the 151 of their papers we have counts for
Showing 2005Show all
3 papers · 1 filter
cs.CG2005
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
Boris Aronov, Prosenjit Bose, Erik D. Demaine +4
We consider preprocessing a set of points in convex position in the plane into a data structure supporting queries of the following form: given a point and a directed l…
cs.DM2005★ 6 cited
Bidimensionality, Map Graphs, and Grid Minors
Erik D. Demaine, MohammadTaghi Hajiaghayi
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial…
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…