Аннотация:Данная работа посвящена двум типам задач регионального поиска. В
первой из этих задач отношением поиска является многогранник в
пространстве $\mathbb{R}^s$. Для этой задачи получена серия
алгоритмов, задаваемых некоторым натуральным параметром. В
зависимости от значения этого параметра получаются различные
оценки памяти и времени, которые дают верхнюю оценку
функциональной сложности в последовательности точек.
Вторая задача --- двумерная задача о близости в евклидовой
метрике. Запросом в этом случае служит круг заданного радиуса $R$.
Для того, чтобы снизить оценку среднего времени в задаче о
близости в евклидовой метрике было предложено ввести новую
характеристику сложности
--- ошибку. Согласившись на некоторую погрешность в
вычислениях, получаем константное среднее время. Для приведенных в
данной работе алгоритмов приближенного поиска средняя ошибка
составляет примерно $0.04$, т.е. на каждые $100$ точек ответа
будем получать не более $4$ ошибочных.