This article is cited in 1 paper

On the functional complexity of the two-dimensional domination problem

È. È. Gasanov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

Keywords: information-graph data model, two-dimensional domination problem, functional complexity, grid method.