The closest neighbour problem on a plane solution using the cellular automata with locators model

This paper describes a cellular automaton with locators which solves the closest neighbor search problem. The problem itself is about finding the closest point from a given finite set to the so-called central cell. Unlike the classic cellular automaton model, cellular automata with locators allow fast signal transmission to any distance. It is proven that such a possibility allows us to solve the problem in a constant time which is fundamentally different from the one dimensional case: the lower complexity estimate for this case is proven to be logarithmic.