Приоритетные R-деревья

Насколько я понял из беглого изучения статей, это весьма шаманские и навороченные алгоритмы, в основе которых лежит всё-таки разбиение всей области на прямоугольные зоны, над которыми строится некая структура данных. Т.е. обычная, евклидова, метрика расстояний заменяется манхеттенской, что на практике в большинстве случаев даёт неплохие результаты, но в худшем случае вряд ли будет существенно лучше O(n).