Ayuda para comprender la búsqueda del árbol Vantage-Point

Question

Esta es mi referencia: http://stevehanov.ca/blog/index.php?id=130

Un árbol de puntos de observación es una forma de organizar un conjunto de puntos para que la búsqueda de los n vecinos más próximos sea lo más eficaz posible. Este árbol se construye eligiendo un punto de un conjunto de puntos (llamado punto de ventaja). La distancia media entre ese punto y todos los demás puntos del espacio es una especie de frontera que divide ese conjunto en dos subconjuntos de igual tamaño. Esto se repite de forma recursiva para cada subconjunto hasta que no quedan más puntos (cuando todos los puntos se han convertido en puntos de observación).

Ahora que busco en un árbol VP es cuando necesito ayuda para entenderlo. Básicamente, cuando se realiza una búsqueda, un nuevo punto se traza en ese espacio de puntos, y usted necesita encontrar los vecinos n-más cercanos a ese punto. Especialmente tengo un problema con la "tau." y su propósito en este algoritmo.

Answer 1

Creo que lo que te puede estar confundiendo es que habla de "el punto más lejano que hemos encontrado" pero en realidad se refiere al punto más lejano de los hasta $n$ candidatos que hemos reunido hasta ahora. Una vez que hayamos recopilado $n$ candidatos, podemos podar todas las partes del árbol que contengan sólo puntos peores que el peor de esos candidatos. Para ello, necesitamos llevar la cuenta de la distancia a nuestro peor candidato hasta el momento. Es decir $\tau$ .

Answer 2

Siempre se busca primero en el subárbol al que pertenece el punto de consulta, en sentido descendente, hasta llegar a una hoja. Cada vez que vuelva de la búsqueda, si la distancia al n-ésimo vecino encontrado hasta ese momento se cruza con el límite del otro subárbol, tendrá que buscar también en el otro subárbol.

La idea es que la distancia al vecino n-ésimo se vaya reduciendo a medida que se desciende para no tener que buscar dentro del otro subárbol (especialmente en los subárboles más cercanos a la raíz del árbol, donde cada subárbol corresponde a muchos puntos excluidos de la búsqueda).

Persuádase dibujando un rectángulo, como su corpus, y un punto de observación como el centro de un disco que denota la distancia media.

Hay dos casos para el punto de consulta: caer en el disco o salir de él. Y dos subcasos para cada caso: el disco centrado en el punto de consulta denota la distancia a su n-ésimo vecino para permanecer dentro del mismo subespacio donde está el punto de consulta, o para intersecar también el otro subespacio.