Access Restriction

Author Chazelle, Bernard
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1990
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of $\textit{n}$ points in $\textit{d}-space$ and a box $[\textit{a}1,$ $\textit{b}1]$ X … X $[\textit{ad},$ $\textit{bd}],$ report every point whose $\textit{i}th$ coordinate lies in [ai, bi], for each $\textit{i}$ = l, … , $\textit{d}.$ The collection of points is fixed once and for all and can be preprocessed. The box, on the other hand, constitutes a query that must be answered online. It is shown that on a pointer machine a query time of $\textit{O}(\textit{k}$ + $polylog(\textit{n})),$ where $\textit{k}$ is the number of points to be reported, can only be achieved at the expense of $&OHgr;(\textit{n}(log$ $\textit{n}/log$ log $\textit{n})\textit{d}-1)$ storage. Interestingly, these bounds are optimal in the pointer machine model, but they can be improved (ever so slightly) on a random access machine. In a companion paper, we address the related problem of adding up weights assigned to the points in the query box.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1990-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 37
Issue Number 2
Page Count 13
Starting Page 200
Ending Page 212

Open content in new tab

   Open content in new tab
Source: ACM Digital Library