Motivación para la compresión de cuadros de rango

En los árboles de cuadros de rango tradicionales (PR Quadtree), cuando un conjunto de puntos está agrupado en una región muy pequeña, se genera una cadena innecesaria de nodos con un solo hijo. Cada uno de estos nodos almacena la misma información espacial, lo que desperdicia espacio y degrada el rendimiento. La compresión busca eliminar esta redundancia.

Representación eficiente con cadenas de bits

Cada celda se representa mediante un código de bits que codifica la ruta desde la raíz hasta ella. Para un árbol de cuadros de 2D, se utiliza un prefijo '1' seguido de pares de bits (00 para SW, 01 para SE, 10 para NW, 11 para NE). Esto permite realizar operaciones de inclusión y cálculo del ancestro común mínimo mediante manipulación de bits, en tiempo constante O(1).

// Ejemplo de codificación de celdas en 2D
using CellCode = uint64_t;
constexpr CellCode ROOT_CODE = 1ULL;
constexpr int QUAD_SW = 0b00; // Suroeste
constexpr int QUAD_SE = 0b01; // Sureste
constexpr int QUAD_NW = 0b10; // Noroeste
constexpr int QUAD_NE = 0b11; // Noreste

// Determina si c1 es subcelda de c2 (c1 ⊆ c2)
bool esSubcelda(CellCode c1, CellCode c2) {
    if (c1 == c2) return true;
    int lv1 = nivelCelda(c1), lv2 = nivelCelda(c2);
    if (lv1 <= lv2) return false;
    return (c1 >> ((lv1 - lv2) * 2)) == c2;
}

Ordenamiento de celdas y la curva Z

La curva Z (código Morton) es una curva de llenado espacial que mapea coordenadas 2D a un orden unidimensional, manteniendo cierta localidad espacial. Se construye intercalando los bits de las coordenadas x e y.

// Genera el código Morton para coordenadas (x,y) con k bits
uint64_t codigoMorton(uint32_t x, uint32_t y, int k) {
    uint64_t resultado = 0;
    for (int i = 0; i < k; i++) {
        resultado |= ((x >> i) & 1ULL) << (2*i);
        resultado |= ((y >> i) & 1ULL) << (2*i + 1);
    }
    return resultado;
}

// Comparación según el orden de la curva Z
bool celdaMenor(CellCode c1, CellCode c2) {
    if (esSubcelda(c1, c2)) return true; // Las subceldas van primero
    if (esSubcelda(c2, c1)) return false;
    CellCode ancestro = ancestroComunMinimo(c1, c2);
    int nivelAncestro = nivelCelda(ancestro);
    // Obtener los cuadrantes inmediatos bajo el ancestro
    int cuad1 = (c1 >> ((nivelCelda(c1) - nivelAncestro - 1) * 2)) & 3;
    int cuad2 = (c2 >> ((nivelCelda(c2) - nivelAncestro - 1) * 2)) & 3;
    // Orden de cuadrantes: SW(0) < NW(1) < SE(2) < NE(3)
    return ordenCuadrante(cuad1) < ordenCuadrante(cuad2);
}

Estructura del árbol comprimido

Un nodo del árbol comprimido almacena dos celdas: la celda grande (L(v)), que es la celda directa del padre, y la celda pequeña (S(v)), donde la subdivisión produce al manos dos cuadrantes no vacíos. Los nodos hoja tienen S(v) igual a la celda del punto.

struct NodoCQT {
    CellCode grande; // L(v): celda grande
    CellCode pequena; // S(v): celda pequeña
    bool esHoja;
    int idPunto;
    NodoCQT* padre;
    std::vector<NodoCQT*> hijos;
};

Construcción del árbol comprimido

Se presentan dos métodos: construcción por división y conquista, y construcción ascendente mediante ordenamiento por curva Z. Ambos tienen complejidad O(d n log n), donde d es la dimensión (2 para 2D).

Algoritmo de inserción

Al insertar una celda C, se busca su sucesor en el árbol binario de búsqueda balanceado (BBST) que mantiene el orden de la curva Z. El ancestro común mínimo antre C y el sucesor determina la posición de inserción.

void insertar(CellCode c) {
    // Buscar el sucesor en el BBST
    NodoCQT* sucesor = encontrarSucesor(c);
    CellCode d = ancestroComunMinimo(c, sucesor->pequena);
    // Insertar según el caso
    NodoCQT* objetivo = buscarNodo(d);
    if (objetivo) {
        // Insertar como hijo directo
        objetivo->hijos.push_back(nuevoNodo);
    } else {
        // Crear nuevo nodo intermedio y reestructurar
    }
}

Algoritmo de eliminación

La eliminación solo se permite en nodos hoja. Si un nodo padre queda con un solo hijo, se elimina y el hijo sobreviviente se conecta directamente al abuelo, sin propagación adicional.

void eliminar(CellCode c) {
    NodoCQT* nodo = buscarNodo(c);
    if (!nodo || !nodo->esHoja) return;
    // Eliminar del BBST y del CQT
    NodoCQT* padre = nodo->padre;
    padre->hijos.erase(std::remove(...));
    // Manejar degeneración del padre
    if (padre->hijos.size() == 1) {
        NodoCQT* abuelo = padre->padre;
        // Reemplazar padre con su único hijo
    }
}

Optimizaciones prácticas

En la implementación real, se sustituye el BBST por una tabla hash basada en el código de celda, logrando acceso O(1). Además, se pueden usar enteros de 128 bits para representar celdas hasta nivel 42, cubriendo escalas de hasta 4×1012:1.

// Uso de hash para acceso directo
std::unordered_map<CellCode, NodoCQT*> tablaHash;

// Ejemplo de cálculo de ancestro común mínimo
CellCode ancestroComunMinimo(CellCode c1, CellCode c2) {
    while (c1 != c2) {
        if (nivelCelda(c1) > nivelCelda(c2)) c1 >>= 2;
        else if (nivelCelda(c2) > nivelCelda(c1)) c2 >>= 2;
        else { c1 >>= 2; c2 >>= 2; }
    }
    return c1;
}

Este diseño permite manejar eficientemente consultas espaciales y operaciones de actualización en aplicaciones como simulaciones de N-cuerpos y bases de datos geoespaciales.