В работе описывается способ модификации R-дерева, заключающийся в переводе узлов дерева в относительную систему координат, где центром координат для каждого из узлов является определенная точка его прямого родителя. Подобная модификация позволяет перемещать хранящиеся в дереве объекты на один и тот же вектор за O(log(N)) по времени, где N - высота дерева, и O(1) по памяти. Приводится описание изменений, которые необходимо внести в структуру дерева и функции вставки, удаления и поиска, а также возможные области применения модифицированного дерева.
Гогиян А.Г. (науч. рук. Шинкарук Д.Н.) Описание модификации R-дерева для работы с перемещающимися объектами // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, [2020]. URL: https://kmu.itmo.ru/digests/article/2994