Bren Hall, Room 1420, 1pm

May 25, 2012:

The dynamic convex hull problem was recently solved in
O(lg *n*) time per
operation, and this result is best possible in models of computation
with bounded branching (e.g., algebraic computation trees). From a data
structures point of view, however, such models are considered
unrealistic because they hide intrinsic notions of information in the
input. In the standard word-RAM and cell-probe models of computation, we
prove that the optimal query time for dynamic convex hulls is, in fact,
Θ(lg *n* / lg lg *n*), for
polylogarithmic update time (and word
size). Our lower bound is based on a reduction from the marked-ancestor
problem, and is one of the first data structural lower bounds for a
nonorthogonal geometric problem. Our upper bounds follow a recent trend
of attacking nonorthogonal geometric problems from an
information-theoretic perspective that has proved central to advanced
data structures. Interestingly, our upper bounds are the first to
successfully apply this perspective to dynamic geometric data
structures, and require substantially different ideas from previous work.

(Based on a paper by Demaine and Pǎtraşcu in SoCG 2007.)