En geometría computacional , el primer recorrido más lejano 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 lejos 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, de manera equivalente, 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 codiciosa . [2]
Cada prefijo de un recorrido primero más lejano proporciona un conjunto de puntos ampliamente espaciados y cercanos a todos los puntos restantes. Más precisamente, ningún otro conjunto de puntos iguales puede estar espaciado más del doble, y ningún otro conjunto de puntos iguales puede estar a menos de la mitad de su punto restante más lejano. En parte debido a estas propiedades, los recorridos del punto más lejano tienen muchas aplicaciones, incluida la aproximación del problema del viajante y el problema métrico del centro k . Pueden construirse en tiempo polinomial o (para espacios euclidianos de baja dimensión ) aproximarse en tiempo casi lineal .
Un recorrido primero más lejano 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 distancia máxima posible al conjunto de puntos anteriores 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 puntos del conjunto. Un espacio dado puede tener muchos recorridos diferentes del primero más lejano, dependiendo tanto de la elección del primer punto en la secuencia (que puede ser cualquier punto en el espacio) como de los vínculos para la distancia máxima entre elecciones posteriores. [2]
Los recorridos del punto más lejano pueden caracterizarse por las siguientes propiedades. Fije un número k y considere el prefijo formado por los primeros k puntos del primer recorrido más lejano de cualquier espacio métrico. Sea r la distancia entre el punto final del prefijo y los demás puntos del prefijo. Entonces este subconjunto tiene las dos propiedades siguientes:
Por el contrario, cualquier secuencia que tenga estas propiedades, para todas las elecciones de k , debe ser un recorrido primero más lejano. Estas son las dos propiedades que definen un conjunto Delone , por lo que cada prefijo del primer recorrido más lejano forma un conjunto Delone. [3]
Rosenkrantz, Stearns y Lewis (1977) utilizaron el primer recorrido más lejano para definir la heurística de inserción más lejana para el problema del viajante . Esta heurística encuentra soluciones aproximadas al problema del viajante 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 un borde del recorrido anterior y se reemplaza por un par de bordes a través del punto agregado, de la forma más económica posible. Aunque Rosenkrantz et al. Aunque prueban sólo una relació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 relaciones de aproximación demostrables. [4]
Posteriormente, González (1985) popularizó la misma secuencia de puntos, quien la utilizó como parte de algoritmos de aproximación codiciosa para dos problemas de agrupamiento, en los que el objetivo es dividir 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 métrico del k -centro , 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 del centro k se puede utilizar para modelar la ubicación de estaciones de bomberos dentro de una ciudad, a 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 agrupación, González elige un conjunto de k centros de agrupación seleccionando los primeros k puntos de un recorrido primero más lejano y luego crea agrupaciones asignando cada punto de entrada al centro de agrupación 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 esta agrupación cada punto está dentro de la distancia r de su centro y cada grupo tiene un diámetro como máximo de 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 -agrupación colocaría dos de estos puntos en un solo grupo, con uno de ellos a una distancia de al menos r / 2 desde su centro y con diámetro al menos r . Por tanto, la heurística de González da una relación de aproximación de 2 para ambos problemas de agrupamiento. [3]
La heurística de González fue redescubierta de forma independiente para el problema de centro k métrico por Dyer y Frieze (1985), quienes la aplicaron de manera más general a problemas de centro k ponderado. [5] Otro artículo sobre el problema del centro k de la misma época, Hochbaum & Shmoys (1985), logra la misma relació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 métrico de k -centro, estas aproximaciones son óptimas: la existencia de una heurística de tiempo polinomial con cualquier relació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 para que estén lo más lejos posible. separados entre sí como sea posible. Más precisamente, el objetivo de este problema es elegir k puntos de un espacio métrico dado o de 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 primero más lejano. Si r denota la distancia del k -ésimo punto de 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. Según el principio del casillero , algunos dos puntos de la solución óptima (cualquiera que sea) deben estar a una distancia r del mismo punto entre estos primeros k − 1 puntos elegidos, y (según la desigualdad del triángulo ) a una distancia 2 r entre sí. . Por lo tanto, la solución heurística dada por el primer recorrido más lejano está dentro de un factor de dos del óptimo. [8] [9] [10]
Otras aplicaciones del recorrido más lejano primero incluyen la cuantificación de color (agrupar los colores de una imagen en un conjunto más pequeño de colores representativos), [11] escaneo progresivo de imágenes (elegir un orden para mostrar los píxeles de una imagen de modo que los prefijos de los ordenar produce buenas versiones de menor resolución de toda la imagen en lugar de completar la imagen de arriba a abajo), [12] selección de puntos en el método de hoja de ruta probabilística para la planificación de movimiento , [13] simplificación de nubes de puntos , [14] generación de máscaras para imágenes de medios tonos , [15] [16] agrupamiento jerárquico , [1] encontrar similitudes entre mallas poligonales de superficies similares, [17] elegir objetivos de observación diversos y de alto valor para la exploración de robots submarinos, [18] detección de fallas en redes de sensores , [19] modelado de la diversidad filogenética , [20] emparejamiento de vehículos en una flota heterogénea con las solicitudes de entrega de los clientes, [21] distribución uniforme de observatorios geodésicos en la superficie de la Tierra [22] o de otros tipos de redes de sensores, [23] generación de luces de puntos virtuales en el método de representación de gráficos por computadora de radiosidad instantánea , [24] y estructuras de datos de búsqueda de rango geométrico . [25]
El primer recorrido más lejano de un conjunto de puntos finitos se puede calcular mediante un algoritmo codicioso que mantiene la distancia de cada punto desde los puntos previamente seleccionados, realizando los siguientes pasos: [3]
Para un conjunto de n puntos, este algoritmo toma O ( n 2 ) pasos y O ( n 2 ) cálculos de distancia. [3]
Un algoritmo de aproximación más rápido , dado 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 incluye 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 alejada del punto previamente seleccionado, donde ε puede elegirse como cualquier número positivo. Toma 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 hash sensible a la localidad tiene tiempo de ejecución. Para métricas definidas por caminos más cortos en gráficos no dirigidos ponderados, una construcción incremental aleatoria basada en el algoritmo de Dijkstra logra el tiempo , donde n y m son los números. de vértices y aristas del gráfico 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 que mantener un número infinito de distancias. En su lugar, 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 denominado 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]
