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.