The two-dimensional closest neighbor search problem solution using the cellular automata with locators

This article describes a cellular automaton with locators that solves the problem of finding the nearest neighbour. The problem is to find from a finite set of points the one closest to a predetermined "central" point. In contrast to the classical model of a cellular automaton, in the model under consideration, instantaneous transmission of signals through the ether at an arbitrary distance is allowed. It is shown that this possibility makes it possible to solve the problem in constant time, which is strikingly different from the one-dimensional case, where a logarithmic lower complexity estimate by the minimal distance is obtained.