Реализации алгоритмов/VP-дерево: различия между версиями
Содержимое удалено Содержимое добавлено
РоманСузи (обсуждение | вклад) стаб с ссылками для дальнейшей проработки |
РоманСузи (обсуждение | вклад) дополнение из w:VP-дерево |
||
Строка 3:
'''VP-дерево''' ({{lang-en|vantage-point tree}}) — разновидность [[:w:Двоичное разбиение пространства|BSP-дерева]].
Из первоначального множества берется одна из точек («опорная точка») и выбирается «радиус» R для этой точки. Остальные точки делятся на два подмножества — с расстоянием меньше R до опорной точки, и расстоянием больше R. В каждом из получившихся подмножеств выбирается следующая опорная точка и новый радиус, и т. д., пока количество элементов в каждом из оставшихся подмножеств не станет меньше определенного порогового значения.
Опорные точки и «радиусы» сфер разбиения выбираются так, чтобы дерево получилось максимально сбалансированным.
<!-- в планах -->
| |||