Diapositiva PPT
En primer lugar se tratará el caso bidimensional, donde cada punto se identifica por su valor de x e y en el plano.
- La generalización posterior a más dimensiones resultará sencilla.
Conduce a ordenar primero según el valor de x, y los puntos con idéntico valor de x se ordenan según su valor de y.
Después de ordenar, una búsqueda exacta se realizaría en un tiempo
O (k * log2 N), siendo N el número de registros.
Las inserciones y extracciones se realizarían en un tiempo de
O (k * log2 N) siempre que se elija como estructura de datos árboles equilibrados dinámicamente.