Duda complejidad parte 2 consulta IN-CIRCLE

[MaxAl100]

Tengo una duda respecto a la complejidad máxima permitida en la consulta IN-CIRCLE, ya que en el video de la cápsula se menciona de que hay que encontrar los puntos que posiblemente estén dentro del círculo y luego hay que ir revisando uno a uno si están dentro. Pero, según tengo entendido, esto haría que la consulta fuera O(n), ya que obtiene k*n (con k entre 0 y 1) nodos posibles y luego se revisa cada uno linealmente si están dentro del círculo o no.
Entonces no estoy seguro si se espera que logremos que la complejidad sea log(n) (de alguna manera que no se me ha ocurrido) o si se puede tener complejidad log(n) para encontrar nodos posibles y luego n para revisar si están dentro del círculo o no.

Y pregunta extra, en caso de que sea permitido realizar n para revisar si está dentro del círculo, se puede realizar algo similar para la consulta de IN-YEAR-REGION?

[benjavicente]

Hola!

Lo importante es complejidad de búsqueda promedio de $O(log(n))$, que se logra con árboles. No se busca que se cumpla eso en la complejidad total del algoritmo.

encontrar los puntos que posiblemente estén dentro del círculo y luego hay que ir revisando uno a uno si están dentro. Pero, según tengo entendido, esto haría que la consulta fuera O(n), ya que obtiene k*n (con k entre 0 y 1) nodos posibles y luego se revisa cada uno linealmente si están dentro del círculo o no.

Puedes considerar la complejidad de eso como $O(log(n) + k)$, donde $k$ es el número de resultados. Si la cantidad a revisar es un factor multiplicado por la cantidad de resultados, y no del tamaño total del conjunto, la complejidad sería también $O(log(n) + k)$, a pesar de que tengas que revisar puntos extra.

También, nota que el $k$ es imposible de sacarlo porque tienes que imprimir los $k$ resultados, y suele ser despreciable con $n$.

Y pregunta extra, en caso de que sea permitido realizar n para revisar si está dentro del círculo, se puede realizar algo similar para la consulta de IN-YEAR-REGION?

No, debes usar árboles para ese supuesto $n$, que en realidad serían los $k$ resultados de IN-YEAR, resulte una búsqueda de complejidad $O(log(n))$ y no $O(log(n) + r)$ con $r$ dependiendo del número de regiones.

Como hint, puedes ver la I1 del semestre pasado, y ver como se maneja árboles con 2 elementos 👀

[MaxAl100]

Entonces para IN-CIRCLE no se debe usar IN-X-RANGE? Porque esto también permitiría obtener todos los nodos posibles (en un rango x) y luego revisar si están dentro del círculo (claro, puede que estén muy lejos)

[benjavicente]

No tan directamente, debería existir un filtro rápido de los elementos en el eje Y, no necesariamente perfecto. Porque si no me equivoco, ocurre que sin filtrar, sería más o menos $O(log(n) + j + k)$, donde ese $j$ es $O(n) \geq O(j) \geq O(k)$. Para imaginárselo, si un círculo es muy chico, se tendría que recorrer la cantidad de resultados $k$ por todo el espacio que queda en el eje Y, que depende de $n$ (no linealmente).