A Lower Bound on Complexity of a Locator Cellular Automaton Solution for the Closest Neighbor Search Problem
Денис Игоревич Васильев, E. E. Gasanov · Moscow University Mathematics Bulletin · 2023
Abstract The paper considers the application of the locator cellular automaton model to the closest neighbor search problem. The locator cellular automaton model assumes the possibility for each cell to translate a signal through any distance using the ether. It was proven earlier that the ether model allows solving the problem with logarithmic time. In this paper we have derived a logarithmic lower bound for this problem.