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

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

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

Подробиці

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

Див. також: Двійковий пошук