Aarhus University Seal

On Range Searching in the Group Model and Combinatorial Discrepancy

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
In this paper we establish an intimate connection between dynamic range searching in the group model and combinatorial discrepancy. Our result states that, for a broad class of range searching data structures (including all known upper bounds), it must hold that $t_ut_q = Omega(disc^2/lg n)$ where $t_u$ is the worst case update time, $t_q$ the worst case query time and $disc$ is the combinatorial discrepancy of the range searching problem in question. This relation immediately implies a whole range of exceptionally high and near-tight lower bounds for all of the basic range searching problems. We list a few of them in the following:begin{itemize}item For half space range searching in $d$-dimensional space, we get a lower bound of $t_u t_q = Omega(n^{1-1/d}/lg n)$. This comes within a $lg n lg lg n$ factor of the best known upper bound. item For orthogonal range searching in $d$-dimensional space, we get a lower bound of $t_u t_q = Omega(lg^{d-2+mu(d)}n)$, where $mu(d)>0$ is some small but strictly positive function of $d$.item For ball range searching in $d$-dimensional space, we get a lower bound of $t_u t_q = Omega(n^{1-1/d}/lg n)$.end{itemize}We note that the previous highest lower bound for any explicit problem, due to P{v a}tra{c s}cu [STOC'07], states that $t_q =Omega((lg n/lg(lg n+t_u))^2)$, which does however hold for a less restrictive class of data structures. Our result also has implications for the field of combinatorial discrepancy. Using textbook range searching solutions, we improve on the best known discrepancy upper bound for axis-aligned rectangles in dimensions $d geq 3$.
Original languageEnglish
Title of host publication2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)
Number of pages8
PublisherIEEE Computer Society Press
Publication year2011
Pages542-549
ISBN (print)978-1-4577-1843-4
DOIs
Publication statusPublished - 2011
Event52nd Annual IEEE Symposium on Foundations of Computer Science. FOCS 2011 - Palm Springs, CA, United States
Duration: 22 Oct 201125 Oct 2011

Conference

Conference52nd Annual IEEE Symposium on Foundations of Computer Science. FOCS 2011
LandUnited States
ByPalm Springs, CA
Periode22/10/201125/10/2011

See relations at Aarhus University Citationformats

ID: 41947980