APPROXIMATE HALFSPACE RANGE COUNTING
We present a simple scheme extending the shallow partitioning data structures of Matousek, which supports efficient approximate halfspace range-counting queries in R(d) with relative error epsilon. Specifically, the problem is, given a set P of n points in R(d), to preprocess them into a data structure that returns, for a query halfspace h, a number t so that (1- epsilon)vertical bar h boolean AND P vertical bar   0, and answers a query in time O(epsilon(-gamma)n(1-1)/(left perpendicular d/2 right perpendicular) 2(b) (log)* (n)) for any gamma > 2/left perpendicular d/2 right perpendicular; 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.
range counting geometric algorithms relative approximations range searching approximation algorithms partition trees shallow partition trees cuttings shallow cuttings hyper-plane arrangements geometric sampling