Data imprecision under λ-geometry model: Range searching problem

Because of constraints in exact modeling, measuring and computing, it is inevitable that algorithms that solve real world problems have to avoid errors. Hence, proposing models to handle error, and designing algorithms that work well in practice, are challenging fields. In this paper, we introduce a model called the λ-geometry model   to handle a dynamic form of imprecision, which allows the precision to change monotonically in the input data of geometric algorithms. λ-geometry is a generalization of region-based models and provides the output of problems as functions, with respect to the level of precision. This type of output helps to design exact algorithms and is also useful in decision making processes. Furthermore, we study the problem of orthogonal range searching in one and two dimensional space under the model of λ-geometry, and propose efficient algorithms to solve it