Approximate Range Searching: The Absolute Model*

Abstract Range searching is a well known problem in the area of geometric data structures. Weconsider this problem in the context of approximation, where an approximation parameter "> 0 is provided. Most prior work on this problem has focused on the case of relative errors,where each range shape R is bounded, and points within distance " * diam(R) of the range'sboundary may or may not be included. We consider a different approximation model, calle