APPROACH FOR 2D POINT LOCATION PROBLEM ON A REGULAR GRID

Abstract

Point location problems often arise in areas such as object visibility analysis, sensor location, human flow simulation, urban planning, mobile control, and paint and film application. In many such problems, it is often necessary to define a set of points that cover given positions, such as viewpoints on the observed surface. This problem can be considered in terms of finding the set of sensor positions, which provides maximum coverage of the points of the set by some criterion of reachability, which is formulated in the paper on the basis of the Euclidean metric. Usually, the object location problem does not have an exact solution, so in practice, optimization methods are used to solve it, which do not guarantee finding a global optimum solution. This makes it necessary to find more effective methods for solving point location problems. The paper presents a method of solving the problem of location of a set of points, which provides a given coverage of the input point set by the criterion of reachability based on drawing circles on a regular (pixel) grid, and determining the grid points that belong to such circles. The presented method allows to solve such problems in a linear time from the number of points of the input set. The main iterations of the algorithm for finding a set of points covering a given set are presented, an experimental study on test point sets on a plane is performed, and examples of the obtained solutions are given. The presented approach consists of the following steps: formation of the criterion of mutual reach of points; determining the dimensions of the pixel grid and the battery array; drawing circles of a given radius on the grid; determination of points belonging to the applied circles; increment of values in the accumulator.Keywords: placement problem, point set, mutual reachability of points, pixel grid, coverage of point set.