Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
Haim Y. Kaplan, Micha Sharir · 2006
Abstract We present new algorithms for approximate range counting,where, for a specified "> 0, we want to count the number of data points in a query range, up to relative error of". We first describe a general framework, adapted from Cohen [10], for this task, and then specialize it to two important instances of range counting: halfspaces in R3 anddisks in the plane. The technique reduces the approximate