Paper Info
Title
Approximate Halfspace Range Counting
Abstract
We present a simple scheme extending the shallow partitioning data structures of Matoušek, which supports efficient approximate halfspace range-counting queries in $\mathbb{R}^d$ with relative error $\varepsilon$. Specifically, the problem is, given a set $P$ of $n$ points in $\mathbb{R}^d$, to preprocess them into a data structure that returns, for a query halfspace $h$, a number $t$ so that $(1-\varepsilon)|h\cap P|\leq t\leq(1+\varepsilon)|h\cap P|$. One of our data structures requires linear storage and $O(n^{1+\delta})$ preprocessing time, for any $\delta0$, and answers a query in time $O(\varepsilon^{-\gamma}n^{1-1/\lfloor d/2\rfloor}2^{b\log^\ast n})$ for any $\gamma2/\lfloor d/2\rfloor$; the choice of $\gamma$ and $\delta$ affects $b$ and the implied constants. Several variants and extensions are also discussed. As presented, the construction of the structure is mostly deterministic, except for one critical randomized step, and so are the query, storage, and preprocessing costs. The quality of approximation, for every query, is guaranteed with high probability. The construction can also be fully derandomized, at the expense of increasing preprocessing time.
Year
DOI
Venue
2010
10.1137/080736600
SIAM J. Comput.
Keywords
Field
DocType
preprocessing cost,query halfspace,cap p,approximate halfspace range,ast n,preprocessing time,linear storage,shallow partitioning data structure,data structure,critical randomized step,efficient approximate halfspace,relative error,cuttings,approximation algorithms,range searching
Approximation algorithm,Discrete mathematics,Data structure,Combinatorics,Storage structure,Range searching,Linear complex structure,Probability distribution,Partition (number theory),Mathematics,Approximation error
Journal
Volume
Issue
ISSN
39
7
0097-5397
Citations 
PageRank 
References 
7
0.50
20
Authors
2
Name
Order
Citations
PageRank
Boris Aronov11430149.20
Micha Sharir284051183.84