Семинар №15

Докладчик: М. Р. Агаев

Тема доклада: "KD-деревья"

Дата: 16.04.2024

Время: 14:30

Место: ул. Союзная 144, 7 корпус ЯрГУ им. П.Г. Демидова, аудитория 315.

Аннотация: Поговорим о такой интересной структуре данных как Kd-дерево.
Довольно мощный инструмент в вычислительной геометрии (один из широко известных примеров его применения: позволяет быстро найти для произвольной точки ближайшего соседа из заданного набора точек). Расскажу во всех подробностях про его построение, 2 основных типа задач, которые решаются этой структурой, временную сложность всего этого.
Для того, чтобы полностью прочувствовать особенность этой структуры, в конце поглядим на программу, написанную мной для этого семинара. (В качестве бонуса расскажу про интересную задачу, которую придумал по ходу написания программы и решал её техникой динамического программирования).
На мой взгляд это может быть полезно для всех, начиная с тех, кто занимается научной и промышленной разработкой (3д моделированием, например), заканчивая олимпиадниками.

Ссылка на запись семинара: https://youtu.be/x_d6EQc6mKg