Approximate range searching: The absolute model (Q2269144)

The problem of range searching of a given geometric region \(R\) is considered in the scope of approximation with given approximation parameter \(\epsilon>0\). Unlike the existing approximation models, the new approach of the absolute model is applied. A variety of range spaces is are considered: halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. Also, different problem formulations are used: range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness.