Paper by Erik D. Demaine

Erik D. Demaine and Mihai Pǎtraşcu, “Tight Bounds for Dynamic Convex Hull Queries (Again)”, in Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007), Gyeongju, South Korea, June 6–8, 2007, pages 354–363.

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.

The paper is available in PostScript (488k), gzipped PostScript (196k), and PDF (332k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.