Аннотация:В работе Ивана Бабинова рассматривается следующая задача. Имеется база данных, состоящая из точек плоскости. В качестве запроса поступает произвольная полуплоскость. Необходимо найти хотя бы одну точку из базы, принадлежащую этой полуплоскости, или сказать, что такой точки нет. Получен линейный по памяти алгоритм решения этой задачи с логарифмическим временем поиска. Показано, что в предлагаемую структуру данных может быть добавлена новая точка за линейное от размера данных время. Также рассмотрен случай, когда точки базы данных движутся во времени прямолинейно и равномерно. Введено понятие состояния базы данных, как упорядоченное множество точек на выпуклой оболочке базы данных. С течением времени состояние базы данных меняется. Показано, что любая база данных проходит конечное число состояний, и через какое-то время попадает в финальное состояние, из которого далее не выходит. Получены верхние и нижние оценки на число состояний базы данных, совпадающие по порядку.