En geometría computacional , el recorrido más lejano primero de un espacio métrico compacto es una secuencia de puntos en el espacio, donde el primer punto se selecciona arbitrariamente y cada punto sucesivo está lo más alejado posible del conjunto de puntos previamente seleccionados. El mismo concepto también se puede aplicar a un conjunto finito de puntos geométricos, restringiendo los puntos seleccionados para que pertenezcan al conjunto o, equivalentemente, considerando el espacio métrico finito generado por estos puntos. [1] Para un espacio métrico finito o un conjunto finito de puntos geométricos, la secuencia resultante forma una permutación de los puntos, también conocida como permutación voraz . [2]
Cada prefijo de un recorrido de punto más lejano primero proporciona un conjunto de puntos que está ampliamente espaciado y cerca de todos los puntos restantes. Más precisamente, ningún otro conjunto de puntos con la misma cantidad puede estar espaciado más del doble de amplio, y ningún otro conjunto de puntos con la misma cantidad puede estar a menos de la mitad de distancia de su punto restante más lejano. En parte debido a estas propiedades, los recorridos de punto más lejano tienen muchas aplicaciones, incluida la aproximación del problema del viajante de comercio y el problema del centro k métrico . Pueden construirse en tiempo polinomial o (para espacios euclidianos de baja dimensión ) aproximarse en tiempo casi lineal .
Un recorrido de primer orden es una secuencia de puntos en un espacio métrico compacto , en el que cada punto aparece como máximo una vez. Si el espacio es finito, cada punto aparece exactamente una vez y el recorrido es una permutación de todos los puntos del espacio. El primer punto de la secuencia puede ser cualquier punto del espacio. Cada punto p después del primero debe tener la máxima distancia posible al conjunto de puntos anterior a p en la secuencia, donde la distancia de un punto a un conjunto se define como el mínimo de las distancias por pares a los puntos del conjunto. Un espacio dado puede tener muchos recorridos de primer orden diferentes, dependiendo tanto de la elección del primer punto de la secuencia (que puede ser cualquier punto del espacio) como de los empates para la distancia máxima entre las elecciones posteriores. [2]
Los recorridos de punto más lejano pueden caracterizarse por las siguientes propiedades. Fijemos un número k y consideremos el prefijo formado por los primeros k puntos del recorrido más lejano de cualquier espacio métrico. Sea r la distancia entre el punto final del prefijo y los otros puntos del prefijo. Entonces, este subconjunto tiene las siguientes dos propiedades:
Por el contrario, cualquier secuencia que tenga estas propiedades, para todas las opciones de k , debe ser un recorrido más lejano primero. Estas son las dos propiedades definitorias de un conjunto Delone , por lo que cada prefijo del recorrido más lejano primero forma un conjunto Delone. [3]
Rosenkrantz, Stearns y Lewis (1977) utilizaron el recorrido más lejano primero para definir la heurística de inserción más lejana para el problema del viajante de comercio . Esta heurística encuentra soluciones aproximadas al problema del viajante de comercio construyendo un recorrido en un subconjunto de puntos, agregando un punto a la vez al recorrido en el orden dado por un recorrido más lejano primero. Para agregar cada punto al recorrido, se rompe una arista del recorrido anterior y se reemplaza por un par de aristas a través del punto agregado, de la manera más económica posible. Aunque Rosenkrantz et al. prueban solo una razón de aproximación logarítmica para este método, muestran que en la práctica a menudo funciona mejor que otros métodos de inserción con mejores razones de aproximación demostrables. [4]
Más tarde, la misma secuencia de puntos fue popularizada por González (1985), quien la utilizó como parte de algoritmos de aproximación voraz para dos problemas de agrupamiento, en los que el objetivo es particionar un conjunto de puntos en k grupos. Uno de los dos problemas que González resuelve de esta manera busca minimizar el diámetro máximo de un grupo, mientras que el otro, conocido como el problema de los k -centros métricos , busca minimizar el radio máximo, la distancia desde un punto central elegido de un grupo hasta el punto más alejado de él en el mismo grupo. Por ejemplo, el problema de los k -centros se puede utilizar para modelar la ubicación de las estaciones de bomberos dentro de una ciudad, con el fin de garantizar que un camión de bomberos pueda llegar rápidamente a todas las direcciones dentro de la ciudad. Para ambos problemas de agrupamiento, González elige un conjunto de k centros de grupos seleccionando los primeros k puntos de un recorrido de más lejos primero, y luego crea grupos asignando cada punto de entrada al centro de grupo más cercano. Si r es la distancia desde el conjunto de k centros seleccionados hasta el siguiente punto en la posición k + 1 en el recorrido, entonces con este agrupamiento cada punto está dentro de la distancia r de su centro y cada grupo tiene un diámetro de como máximo 2 r . Sin embargo, el subconjunto de k centros junto con el siguiente punto están todos a una distancia de al menos r entre sí, y cualquier k -agrupamiento pondría algunos dos de estos puntos en un solo grupo, con uno de ellos a una distancia de al menos r /2 de su centro y con un diámetro de al menos r . Por lo tanto, la heurística de González da una razón de aproximación de 2 para ambos problemas de agrupamiento. [3]
La heurística de González fue redescubierta independientemente para el problema de k -centros métricos por Dyer y Frieze (1985), quienes la aplicaron de manera más general a problemas de k -centros ponderados. [5] Otro artículo sobre el problema de k -centros de la misma época, Hochbaum y Shmoys (1985), logra la misma razón de aproximación de 2, [6] pero sus técnicas son diferentes. [5] Sin embargo, la heurística de González y el nombre "recorrido más lejano primero" a menudo se atribuyen incorrectamente a Hochbaum y Shmoys. [7] Tanto para el problema de agrupamiento de diámetro mínimo-máximo como para el problema de k -centros métricos, estas aproximaciones son óptimas: la existencia de una heurística de tiempo polinomial con cualquier razón de aproximación constante menor que 2 implicaría que P = NP . [3] [6]
Además de para la agrupación, el recorrido más lejano primero también se puede utilizar en otro tipo de problema de ubicación de instalaciones, el problema de dispersión de instalaciones máxima-mínima, en el que el objetivo es elegir las ubicaciones de k instalaciones diferentes de modo que estén lo más alejadas entre sí como sea posible. Más precisamente, el objetivo en este problema es elegir k puntos de un espacio métrico dado o un conjunto dado de puntos candidatos, de tal manera que se maximice la distancia mínima por pares entre los puntos seleccionados. Nuevamente, esto se puede aproximar eligiendo los primeros k puntos de un recorrido más lejano primero. Si r denota la distancia del k ésimo punto desde todos los puntos anteriores, entonces cada punto del espacio métrico o del conjunto candidato está dentro de la distancia r de los primeros k − 1 puntos. Por el principio del palomar , algunos dos puntos de la solución óptima (cualquiera que sea) deben estar dentro de la distancia r del mismo punto entre estos primeros k − 1 puntos elegidos, y (por la desigualdad triangular ) dentro de la distancia 2 r entre sí. Por lo tanto, la solución heurística dada por el recorrido más lejano primero está dentro de un factor de dos del óptimo. [8] [9] [10]
Otras aplicaciones del recorrido más lejano primero incluyen la cuantificación del color (agrupamiento de los colores de una imagen en un conjunto más pequeño de colores representativos), [11] el escaneo progresivo de imágenes (elección de un orden para mostrar los píxeles de una imagen de modo que los prefijos del ordenamiento produzcan buenas versiones de menor resolución de toda la imagen en lugar de rellenar la imagen de arriba a abajo), [12] la selección de puntos en el método de hoja de ruta probabilística para la planificación del movimiento , [13] la simplificación de nubes de puntos , [14] la generación de máscaras para imágenes de medios tonos , [15] [16] el agrupamiento jerárquico , [1] la búsqueda de similitudes entre mallas poligonales de superficies similares, [17] la elección de objetivos de observación diversos y de alto valor para la exploración submarina de robots, [18] la detección de fallos en redes de sensores , [19] el modelado de la diversidad filogenética , [20] la correspondencia de vehículos de una flota heterogénea con las solicitudes de entrega de los clientes, [21] la distribución uniforme de los observatorios geodésicos en la superficie de la Tierra [22] o de otros tipos de redes de sensores, [23] generación de luces puntuales virtuales en el método de renderizado de gráficos por computadora de radiosidad instantánea , [24] y estructuras de datos de búsqueda de rango geométrico . [25]
El recorrido más lejano de un conjunto finito de puntos se puede calcular mediante un algoritmo voraz que mantiene la distancia de cada punto con respecto a los puntos seleccionados previamente, realizando los siguientes pasos: [3]
Para un conjunto de n puntos, este algoritmo requiere O ( n 2 ) pasos y O ( n 2 ) cálculos de distancia. [3]
Un algoritmo de aproximación más rápido , propuesto por Har-Peled y Mendel (2006), se aplica a cualquier subconjunto de puntos en un espacio métrico con dimensión de duplicación acotada , una clase de espacios que incluyen los espacios euclidianos de dimensión acotada. Su algoritmo encuentra una secuencia de puntos en la que cada punto sucesivo tiene una distancia dentro de un factor 1 − ε de la distancia más lejana desde el punto seleccionado previamente, donde ε puede elegirse como cualquier número positivo. Lleva tiempo . [2]
Los resultados para la dimensión de duplicación acotada no se aplican a espacios euclidianos de alta dimensión, porque el factor constante en la notación O grande para estos algoritmos depende de la dimensión. En cambio, un método de aproximación diferente basado en el lema de Johnson-Lindenstrauss y el hashing sensible a la localidad tiene un tiempo de ejecución Para las métricas definidas por caminos más cortos en grafos no dirigidos ponderados, una construcción incremental aleatoria basada en el algoritmo de Dijkstra logra un tiempo , donde n y m son los números de vértices y aristas del grafo de entrada, respectivamente. [26]
Para seleccionar puntos de un espacio continuo como el plano euclidiano , en lugar de un conjunto finito de puntos candidatos, estos métodos no funcionarán directamente, porque habría un número infinito de distancias a mantener. En cambio, cada nuevo punto debe seleccionarse como el centro del círculo vacío más grande definido por el conjunto de puntos previamente seleccionado. [12] Este centro siempre estará en un vértice del diagrama de Voronoi de los puntos ya seleccionados, o en un punto donde un borde del diagrama de Voronoi cruza el límite del dominio. En esta formulación, el método para construir recorridos más lejanos primero también se ha llamado inserción incremental de Voronoi . [27] Es similar al refinamiento de Delaunay para la generación de mallas de elementos finitos , pero difiere en la elección de qué vértice de Voronoi insertar en cada paso. [28]