En geometría computacional , el primer recorrido más lejano de un espacio métrico acotado 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. Para un espacio métrico finito o un conjunto finito de puntos geométricos, la secuencia resultante forma una permutación de los puntos, conocida como permutación codiciosa .
Cada prefijo de un primer recorrido más lejano proporciona un conjunto de puntos que está ampliamente espaciado (dentro de un factor de dos de los espacios más amplios posibles para ese número de puntos) y cerca de todos los puntos restantes (dentro de un factor de dos de la distancia mínima). para esa cantidad de puntos). En parte debido a estas propiedades, recorridos más alejada de punto tienen muchas aplicaciones, incluyendo la aproximación del problema del viajante y la métrica k -center problema. Pueden construirse en tiempo polinomial o (para espacios euclidianos de baja dimensión ) aproximados en tiempo casi lineal .
Definición y propiedades
Un recorrido más lejano es una secuencia de puntos en un espacio métrico acotado , y 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 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 puntos en el conjunto. Un espacio dado puede tener muchos recorridos diferentes, el primero más lejano, dependiendo tanto de la elección del primer punto de la secuencia (que puede ser cualquier punto del espacio) como de los vínculos para la distancia máxima entre las opciones posteriores. [1]
Los recorridos del punto más lejano se pueden caracterizar por las siguientes propiedades. Fije un número k y considere el subconjunto 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 el conjunto de puntos previamente seleccionados. Entonces este subconjunto tiene las siguientes dos propiedades:
- Todos los pares de puntos seleccionados están a una distancia de al menos r entre sí, y
- Todos los puntos de todo el espacio métrico están a una distancia como máximo r del subconjunto.
Por el contrario, cualquier secuencia que tenga estas propiedades 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. [2]
Aplicaciones
Rosenkrantz, Stearns y Lewis (1977) utilizaron por primera vez el recorrido más lejano primero en relación con la heurística para el problema del viajante de comercio . En la heurística de inserción más lejana, discutida por Rosenkrantz et al., Un recorrido se construye de forma incremental, agregando un punto a la vez en el orden dado por un recorrido más lejano primero. Para agregar cada punto al recorrido del vendedor ambulante de los puntos anteriores, esta heurística considera todas las formas posibles de romper un borde del recorrido y reemplazarlo por dos bordes a través del nuevo punto, y elige el más barato de estos reemplazos. Aunque Rosenkrantz et al. demuestran solo 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 probables. [3]
Posteriormente, la misma secuencia de puntos fue popularizada por González (1985) , quien la utilizó como parte de un algoritmo de aproximación ávido para el problema de encontrar k conglomerados que minimicen el diámetro máximo de un conglomerado. El mismo algoritmo se aplica también, con la misma calidad de aproximación, al problema del centro k métrico . Este problema es una de varias formulaciones de análisis de conglomerados y ubicación de instalaciones , en las que el objetivo es dividir un conjunto dado de puntos en k conglomerados diferentes, cada uno con un punto central elegido, de modo que la distancia máxima desde cualquier punto al centro de su grupo se minimiza. Por ejemplo, este problema se puede utilizar para modelar la ubicación de las 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. González describió una heurística de agrupamiento que selecciona como centros los primeros k puntos de un recorrido más lejano primero, y luego asigna cada uno de los puntos de entrada a su centro 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 este agrupamiento alcanza una distancia de 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 colocaría dos de estos puntos en un grupo, por lo que no hay agrupamiento con una distancia mejor que r / 2 . Por lo tanto, la heurística de González da una razón de aproximación de 2 para este problema. [2] Esta heurística, y el nombre "primer recorrido más lejano", a menudo se atribuyen incorrectamente a un artículo diferente del mismo tiempo, Hochbaum & Shmoys (1985) . Sin embargo, Hochbaum y Shmoys utilizaron técnicas de teoría de grafos, no el primer recorrido más lejano, para obtener un algoritmo de aproximación diferente para el centro métrico k con la misma razón de aproximación que la heurística de González. [4] Tanto para el problema de agrupamiento de diámetro mínimo-máximo como para el problema métrico del centro k , 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 . [2] [4]
Además de la agrupación en clústeres, 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áximo-mínimo, en el que el objetivo es elegir las ubicaciones de k instalaciones diferentes para que estén lo más lejos posible. separados unos de otros 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 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 el conjunto candidato está dentro de la distancia r de los primeros k - 1 puntos. Según el principio de 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 (por la desigualdad del triángulo ) dentro de 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. [5] [6] [7]
Otras aplicaciones del primer recorrido más lejano incluyen la cuantificación del color (agrupando los colores de una imagen en un conjunto más pequeño de colores representativos), [8] escaneo progresivo de imágenes (eligiendo un orden para mostrar los píxeles de una imagen de modo que los prefijos del ordenar producir buenas versiones de menor resolución de toda la imagen en lugar de rellenar la imagen de arriba a abajo), [9] selección de puntos en el método de mapa de ruta probabilístico para la planificación del movimiento , [10] simplificación de nubes de puntos , [11] generación de máscaras para imágenes de medios tonos , [12] [13] agrupamiento jerárquico , [14] encontrar las similitudes entre mallas poligonales de superficies similares, [15] planificación de tareas de robots submarinos, [16] detección de fallas en redes de sensores , [17] modelado de diversidad filogenética , [18] hacer coincidir los vehículos de una flota heterogénea con las solicitudes de entrega de los clientes, [19] distribución uniforme de los observatorios geodésicos en la superficie de la Tierra [20] o de otros tipos de redes de sensores, [21] generación de p virtuales luces unidas en el método de representación de gráficos por computadora de radiosidad instantánea , [22] y estructuras de datos de búsqueda de rango geométrico . [23]
Algoritmos
Algoritmo exacto codicioso
El primer recorrido más lejano de un conjunto de puntos finitos puede calcularse mediante un algoritmo codicioso que mantiene la distancia de cada punto desde los puntos seleccionados previamente, realizando los siguientes pasos: [2]
- Inicialice la secuencia de puntos seleccionados a la secuencia vacía y las distancias de cada punto a los puntos seleccionados hasta el infinito.
- Si bien no se han seleccionado todos los puntos, repita los siguientes pasos:
- Escanee la lista de puntos aún no seleccionados para encontrar un punto p que tenga la distancia máxima desde los puntos seleccionados.
- Quite p de los puntos aún no seleccionados y agréguelo al final de la secuencia de puntos seleccionados.
- Para cada punto q restante aún no seleccionado , reemplace la distancia almacenada para q por el mínimo de su valor anterior y la distancia de p a q .
Para un conjunto de n puntos, este algoritmo toma O ( n 2 ) pasos y O ( n 2 ) cálculos de distancia. [2]
Aproximaciones
Un algoritmo de aproximación más rápido , proporcionado 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 previamente seleccionado, donde ε se puede elegir para que sea cualquier número positivo. Toma tiempo. [1]
Los resultados para la dimensión de duplicación acotada no se aplican a los 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ónPara métricas definidas por rutas más cortas 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 grafo de entrada, respectivamente. [24]
Inserción incremental de Voronoi
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 que mantener. 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. [9] 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 de Voronoi incremental . [25] 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. [26]
Ver también
- Algoritmo de Lloyd , un método diferente para generar puntos espaciados uniformemente en espacios geométricos
Referencias
- ↑ a b Har-Peled, S .; Mendel, M. (2006), "Construcción rápida de redes en métricas de baja dimensión, y sus aplicaciones", SIAM Journal on Computing , 35 (5): 1148-1184, arXiv : cs / 0409057 , doi : 10.1137 / S0097539704446281 , Señor 2217141
- ^ a b c d e González, TF (1985), "Agrupamiento para minimizar la distancia máxima entre grupos", Ciencias de la computación teóricas , 38 (2-3): 293-306, doi : 10.1016 / 0304-3975 (85) 90224-5 , MR 0807927
- ^ Rosenkrantz, DJ; Stearns, RE; Lewis, PM, II (1977), "Un análisis de varias heurísticas para el problema del viajante de comercio", SIAM Journal on Computing , 6 (3): 563–581, doi : 10.1137 / 0206041 , MR 0459617
- ^ a b Hochbaum, Dorit S .; Shmoys, David B. (1985), "Una mejor heurística posible para el problema del centro k ", Matemáticas de la investigación de operaciones , 10 (2): 180-184, doi : 10.1287 / moor.10.2.180 , MR 0793876
- ^ White, Douglas J. (1991), "El problema de máxima dispersión", IMA Journal of Mathematics Applied in Business and Industry , 3 (2): 131-140 (1992), doi : 10.1093 / imaman / 3.2.131 , MR 1154657; White acredita el uso del primer recorrido más lejano como una heurística para que este problema Steuer, RE (1986), Optimización de criterios múltiples: teoría, cálculo y aplicaciones , Nueva York: Wiley
- ^ Tamir, Arie (1991), "Ubicación de instalaciones desagradables en gráficos", SIAM Journal on Discrete Mathematics , 4 (4): 550–567, doi : 10.1137 / 0404048 , MR 1129392
- ^ Ravi, SS; Rosenkrantz, DJ; Tayi, GK (1994), "Algoritmos heurísticos y de casos especiales para problemas de dispersión", Investigación de operaciones , 42 (2): 299–310, doi : 10.1287 / opre.42.2.299 , JSTOR 171673
- ^ Xiang, Z. (1997), "Cuantización de imágenes en color minimizando la distancia máxima entre grupos", Transacciones de ACM en gráficos , 16 (3): 260–276, doi : 10.1145 / 256157.256159
- ^ a b Eldar, Y .; Lindenbaum, M .; Porat, M .; Zeevi, YY (1997), "La estrategia del punto más lejano para el muestreo progresivo de imágenes", IEEE Transactions on Image Processing , 6 (9): 1305-1315, Bibcode : 1997ITIP .... 6.1305E , doi : 10.1109 / 83.623193
- ^ Mazer, E .; Ahuactzin, JM; Bessiere, P. (1998), "El algoritmo de la clave de Ariadne", Journal of Artificial Intelligence Research , 9 : 295–316, doi : 10.1613 / jair.468
- ^ Moenning, C .; Dodgson, NA (2003), "Un nuevo algoritmo de simplificación de la nube de puntos", 3ra Conferencia internacional IASTED sobre visualización, procesamiento de imágenes y procesamiento de imágenes
- ^ Gotsman, Craig; Allebach, Jan P. (1996), "Límites y algoritmos para pantallas de tramado" (PDF) , en Rogowitz, Bernice E .; Allebach, Jan P. (eds.), Visión humana e imágenes electrónicas , Proc. SPIE, 2657 , págs. 483–492, doi : 10.1117 / 12.238746
- ^ Shahidi, R .; Moloney, C .; Ramponi, G. (2004), "Diseño de máscaras del punto más lejano para medios tonos de imagen", EURASIP Journal on Applied Signal Processing , 12 : 1886–1898, Bibcode : 2004EJASP2004 ... 45S , doi : 10.1155 / S1110865704403217
- ^ Dasgupta, S .; Long, PM (2005), "Garantías de rendimiento para agrupaciones jerárquicas", Journal of Computer and System Sciences , 70 (4): 555–569, doi : 10.1016 / j.jcss.2004.10.006 , MR 2136964
- ^ Lipman, Y .; Funkhouser, T. (2009), "Möbius votando por correspondencia de superficie", Proc. ACM SIGGRAPH , págs. 72: 1–72: 12, doi : 10.1145 / 1576246.1531378
- ^ Girdhar, Y .; Giguère, P .; Dudek, G. (2012), "Exploración submarina adaptativa autónoma utilizando modelado de temas en línea" (PDF) , Proc. En t. Symp. Robótica experimental
- ^ Altinisik, U .; Yildirim, M .; Erkan, K. (2012), "Aislar fallas de sensor no predefinidas mediante el uso del algoritmo de primer recorrido más lejano", Ing. Ind. Chem. Res. , 51 (32): 10641–10648, doi : 10.1021 / ie201850k
- ^ Bordewich, Magnus; Rodrigo, Allen; Semple, Charles (2008), "Selección de taxones para guardar o secuenciar: criterios deseables y una solución codiciosa", Biología Sistemática , 57 (6): 825–834, doi : 10.1080 / 10635150802552831
- ^ Fisher, Marshall L .; Jaikumar, Ramchandran (1981), "Una heurística de asignación generalizada para el enrutamiento de vehículos", Networks , 11 (2): 109-124, doi : 10.1002 / net.3230110205 , MR 0618209; citado por Gheysens, Filip; Golden, Bruce; Assad, Arjang (1986), "Una nueva heurística para determinar el tamaño y la composición de la flota", en Gallo, Giorgio; Sandi, Claudio (eds.), Netflow en Pisa , Estudios de programación matemática, 26 , Springer, págs. 233-236, doi : 10.1007 / bfb0121103
- ^ Hase, Hayo (2000), "Nuevo método para la selección de sitios adicionales para la homogeneización de una distribución puntual cosférica no homogénea", en Rummel, Reinhard; Drewes, Hermann; Bosch, Wolfgang; et al. (eds.), Towards an Integrated Global Geodetic Observing System (IGGOS): IAG Section II Symposium Munich, 5-9 de octubre de 1998, Carteles - Sesión B , Asociación Internacional de Simposios de Geodesia, Springer, págs. 180-183, doi : 10.1007 / 978-3-642-59745-9_35
- ^ Vieira, Luiz Filipe M .; Vieira, Marcos Augusto M .; Ruiz, Linnyer Beatrys ; Loureiro, Antonio AF; Silva, Diógenes Cecílio; Fernandes, Antônio Otávio (2004), "Algoritmo de implementación de redes de sensores incrementales eficientes" (PDF) , Proc. Symp brasileño. Redes de computadoras , págs. 3-14
- ^ Laine, Samuli; Saransaari, Hannu; Kontkanen, Janne; Lehtinen, Jaakko; Aila, Timo (2007), "Radiosidad instantánea incremental para iluminación indirecta en tiempo real", Actas de la 18ª Conferencia Eurográfica sobre Técnicas de Representación (EGSR'07) , Aire-la-Ville, Suiza, Suiza: Asociación Eurográfica, págs. 277 –286, doi : 10.2312 / EGWR / EGSR07 / 277-286 , ISBN 978-3-905673-52-4
- ^ Abbar, S .; Amer-Yahia, S .; Indyk, P .; Mahabadi, S .; Varadarajan, KR (2013), "Problema diverso del vecino cercano", Actas del 29º Simposio Anual sobre Geometría Computacional , págs. 207–214, doi : 10.1145 / 2462356.2462401 , hdl : 1721.1 / 87000
- ^ Eppstein, David ; Har-Peled, Sariel ; Sidiropoulos, Anastasios (2020), "Agrupación codiciosa aproximada y selección de distancia para métricas de gráficos", Journal of Computational Geometry , 11 (1): 629–652, doi : 10.20382 / jocg.v11i1a25 , MR 4194877
- ^ Teramoto, Sachio; Asano, Tetsuo ; Katoh, Naoki; Doerr, Benjamin, "Inserting points uniformly at every instance" , Transacciones de IEICE sobre información y sistemas , E89-D (8): 2348–2356, Bibcode : 2006IEITI..89.2348T , doi : 10.1093 / ietisy / e89-d.8.2348
- ^ Ruppert, Jim (1995), "Un algoritmo de refinamiento de Delaunay para la generación de mallas bidimensionales de calidad", Journal of Algorithms , 18 (3): 548–585, doi : 10.1006 / jagm.1995.1021