Поиск ближайшего соседа на плоскости с помощью клеточного автомата с локаторами

В данной статье описывается клеточный автомат с локаторами, решающий задачу поиска ближайшего соседа. Задача заключается в том, чтобы из конечного множества точек выделить одну, самую близкую к заранее определенной "центральной" точке. В отличие от классической модели клеточного автомата, в рассматриваемой модели допускается мгновенная передача сигналов через эфир на произвольное расстояние. Показано, что такая возможность позволяет решить задачу за константное время, что в корне отличается от одномерного случая, где получена логарифмическая по искомому расстоянию нижняя оценка сложности.