NDLI: On Range Searching in the Group Model and Combinatorial Discrepancy

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Larsen, Kasper Green
Copyright Year	2014
Abstract	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_u t_q=\Omega(\mbox{disc}^2)$, where $t_u$ is the worst case update time, $t_q$ is 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: (1) For $d$-dimensional halfspace range searching, we get a lower bound of $t_u t_q=\Omega(n^{1-1/d})$. This comes within an lg lg $n$ factor of the best known upper bound. (2) For orthogonal range searching, we get a lower bound of $t_u t_q=\Omega(\mbox{lg}^{d-1}n)$. (3) For ball range searching, we get a lower bound of $t_u t_q=\Omega(n^{1-1/d})$. We note that the previous highest lower bound for any explicit problem, due to Pǎtraşcu [Proceedings of the 39th ACM Symposium on Theory of Computation, 2007, pp. 40--46], states that $t_q=\Omega((\mbox{lg} n/\mbox{lg}(\mbox{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 all dimensions $d\ge 3$.
Starting Page	673
Ending Page	686
Page Count	14
File Format	PDF
ISSN	00975397
DOI	10.1137/120865240
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011))
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-04-29
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems discrepancy computational geometry Data structures range searching lower bounds group model
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in