Some Techniques for Geometric Searching with Implicit Set Representations

Abstract:

There are many efficient ways of searching a set when all its elements can be represented in memory. Often, however, the domain of the search is too large to have each element stored separately and some implicit representation must be used. Whether it is still possible to search efficiently in these conditions
is the underlying theme of this paper. We look at several occurrences of this problem in computational geometry and we propose various lines of attack. In the course of doing so, we improve the solutions of several specific problems; for example, computing order statistics, performing polygonal range searching,
testing algebraic predicates, etc.