Реализации алгоритмов/VP-дерево

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

VP-дерево (англ. vantage-point tree) — разновидность BSP-дерева.

Из первоначального множества берется одна из точек («опорная точка») и выбирается «радиус» R для этой точки. Остальные точки делятся на два подмножества — с расстоянием меньше R до опорной точки, и расстоянием больше R. В каждом из получившихся подмножеств выбирается следующая опорная точка и новый радиус, и т. д., пока количество элементов в каждом из оставшихся подмножеств не станет меньше определенного порогового значения.

Опорные точки и «радиусы» сфер разбиения выбираются так, чтобы дерево получилось максимально сбалансированным.

Ссылки[править]