Approximate Range Searching: The Absolute Model

View/ Open
Date
2007-05-07Author
da Fonseca, Guilherme D.
Mount, David M.
Metadata
Show full item recordAbstract
Range searching is a well known problem in the area of geometric data
structures. 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 case of relative errors, 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 consider a different approximation model,
called the absolute 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 range spaces consisting of halfspaces, Euclidean balls,
simplices, axis-aligned rectangles, and general convex bodies. We consider a
variety of problem formulations, including range searching under general
commutative semigroups, idempotent semigroups, groups, and range emptiness.
We show how idempotence can be used to improve not only approximate, but also
exact halfspace range searching. Our data structures are much simpler than
both their exact and relative model counterparts, and so are amenable to
efficient implementation.