On the functional complexity of the two-dimensional domination problem

In this paper we study the two-dimensional domination problem in which the database is a set of points on the plane, and it is necessary for an arbitrary point of the plane, interpreted as a search query, find all the points from the database, which exceed the query by both coordinates. Functional complexity is the function of the dependence of search time on the memory size. The paper shows how, using the Bentley-Maurer method, we can obtain algorithms with different search time and memory size ratio.