Аннотация:Данная работа посвящена исследованию задачи о поиске движущихся
объектов, которые могут столкнуться с движущимся
объектом-запросом, где под столкновением понимается нахождение
объектов в опасной близости.
Предлагается алгоритм,
решающий задачу об опасной близости для случая фиксированных
скоростей объектов за логарифмическое время. Также
описывается алгоритм решения этой задачи для случая, когда
скорости объектов изменяются в определенном интервале. Показано,
что этот алгоритм имеет сложность операций поиска, вставки,
удаления порядка $\sqrt{N}$, где $N$ - число движущихся объектов.