Approximate Range Searching In The Absolute Error Model

Abstract

Range searching is a well known problem in computational geometry. We consider this problem in the context of approximation, where an approximation parameter eps > 0 is provided. Most prior work on this problem has focused on the relative error model, where each range shape R is bounded, and points within distance eps diam(R) of the range's boundary may or may not be included. We introduce a different approximation model, called the absolute error model, in which points within distance eps of the range's boundary may or may not be included, regardless of the diameter of the range. We consider sets of ranges consisting of general convex bodies, axis-aligned rectangles, halfspaces, Euclidean balls, and simplices. We examine a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, range emptiness, and range reporting. We apply our data structures to several related problems, including range sketching, approximate nearest neighbor searching, exact idempotent range searching, approximate range searching in the data stream model, and approximate range searching in the relative model.