Квадродерево и k-d-дерево

Коротко: Квадродерево и k-d-дерево рекурсивно делят пространство на области, чтобы быстро находить точки вблизи позиции, не проверяя все.

Подробнее: Оба — пространственные индексные структуры. Они отвечают на вопросы «какие точки лежат в этом прямоугольнике?» или «какая точка ближайшая?» примерно за O(log n) вместо O(n).

Подробности

• Квадродерево: Делит плоскость на четыре равных квадранта, которые при необходимости делятся дальше. Популярно в играх (проверка столкновений), картографических плитках и сжатии изображений. Трёхмерный вариант — октодерево.
• k-d-дерево: Двоичное дерево, делящее по медиане поочерёдно по одной координате (x, затем y, затем z, …). Хорошо для поиска ближайших соседей в малых размерностях.
• Предел: При очень многих измерениях (около 20+) они теряют преимущество («проклятие размерности»). Тогда используют векторные индексы с приближёнными методами.
• Родственное: R-деревья для прямоугольников (PostGIS), geohash для карт.
• Движущиеся объекты: Их нужно удалять из дерева и вставлять заново, что может быть дорого.

См. также: Двоичный поиск