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

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