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 Lower bounds on the complexity of orthogonal range searching in thestatic case are established. Specifically, we consider the followingdominance search problem: Given a collection of<?Pub Fmt italic>n<?Pub Fmt /italic> weighted points in<?Pub Fmt italic>d<?Pub Fmt /italic>-space and a query point<?Pub Fmt italic>q<?Pub Fmt /italic>, compute the cumulative weight ofthe points dominated (in all coordinates) by<?Pub Fmt italic>q<?Pub Fmt /italic>. It is assumed that the weights arechosen in a commutative semigroup and that the query time measures onlythe number of arithmetic operations needed to compute the answer. It isproved that if <?Pub Fmt italic>m<?Pub Fmt /italic> units of storage areavailable, then the query time is at least proportional to (log<?Pub Fmt italic>n<?Pub Fmt /italic>/log(2<?Pub Fmt italic>m<?Pub Fmt /italic>/<?Pub Fmt italic>n<?Pub Fmt /italic>))<?Pub Fmt italic>d<?Pub Fmt /italic>–<?Pub Caret1>1in both the worst and average cases. This lower bound is provably tightfor <?Pub Fmt italic>m<?Pub Fmt /italic> =&OHgr;(<?Pub Fmt italic>n<?Pub Fmt /italic>(log<?Pub Fmt italic>n<?Pub Fmt /italic>)<?Pub Fmt italic>d<?Pub Fmt /italic>–1+ε) and any fixed ε> 0. A lower bound of &OHgr;(<?Pub Fmt italic>n<?Pub Fmt /italic>/loglog<?Pub Fmt italic>n<?Pub Fmt /italic>)<?Pub Fmt italic>d<?Pub Fmt /italic>)on the time required for executing <?Pub Fmt italic>n<?Pub Fmt /italic>inserts and queries is also established. —Author's Abstract
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-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 37
Issue Number 3
Page Count 25
Starting Page 439
Ending Page 463

Open content in new tab

   Open content in new tab
Source: ACM Digital Library