This article is cited in 2 papers

Part 2. Mathematics and Computer Science

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

D. I. Vasilyev

Lomonosov Moscow State University

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

Keywords: cellular automaton with locators, homogeneous structures, the closest neighbour search.