Recorrido más lejano primero

Secuencia de puntos alejados de los puntos anteriores

Los primeros cinco puntos de un recorrido de punto más lejano de un conjunto de puntos planos. El primer punto se elige arbitrariamente y cada punto sucesivo está lo más alejado posible de todos los puntos elegidos previamente.

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 .

Definición y propiedades

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:

• Todos los pares de puntos seleccionados están a una distancia al menos r entre sí, y
• Todos los puntos del espacio métrico están a una distancia máxima r del subconjunto.

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]

Aplicaciones

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 primero el más lejano y luego crea grupos asignando cada punto de entrada al centro del 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 puntos de luz 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]

Algoritmos

Algoritmo exacto codicioso

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]

• Inicializa la secuencia de puntos seleccionados en la secuencia vacía y las distancias de cada punto a los puntos seleccionados hasta el infinito.
• Aunque no se hayan 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.
  • Elimina p de los puntos aún no seleccionados y agrégalo 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 requiere O ( n ² ) pasos y O ( n ² ) cálculos de distancia. ^[3]

Aproximaciones

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] ${\displaystyle O(n\log n)}$

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] ${\displaystyle O(\varepsilon ^{-2}n^{1+1/(1+\varepsilon )^{2}+o(1)}).}$ ${\displaystyle O(\varepsilon ^{-1}m\log n\log {\tfrac {n}{\varepsilon }})}$

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 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]

Véase también

• Algoritmo de Lloyd , un método diferente para generar puntos espaciados uniformemente en espacios geométricos

Referencias

1. Dasgupta, S.; Long, PM (2005), "Garantías de rendimiento para agrupamiento jerárquico", Journal of Computer and System Sciences , 70 (4): 555–569, doi : 10.1016/j.jcss.2004.10.006 , MR  2136964
2. 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, MR  2217141, S2CID  37346335
3. Gonzalez, TF (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR  0807927
4. 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, S2CID  14764079
5. Dyer, ME ; Frieze, AM (1985), "Una heurística simple para el problema del p-centro" (PDF) , Operations Research Letters , 3 (6): 285–288, doi :10.1016/0167-6377(85)90002-1, MR  0797340
6. Hochbaum, Dorit S. ; Shmoys, David B. (1985), "La 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
7. Para ejemplos destacados de atribución incorrecta de la heurística del más lejano primero a Hochbaum y Shmoys (1985), véase, por ejemplo,
   • Dasgupta, Sanjoy (2002), "Garantías de rendimiento para la agrupación jerárquica", en Kivinen, Jyrki; Sloan, Robert H. (eds.), Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, 8-10 de julio de 2002, Actas , Lecture Notes in Computer Science, vol. 2375, Springer, págs. 351–363, doi :10.1007/3-540-45435-7_24, ISBN 978-3-540-43836-6(corregido en la versión de revista de 2005 del mismo artículo)
   • Agarwal, Sameer; Ramamoorthi, Ravi; Belongie, Serge J.; Jensen, Henrik Wann (2003), "Muestreo de importancia estructurado de mapas ambientales", ACM Trans. Graph. , 22 (3): 605–612, doi :10.1145/882262.882314
   • Baram, Yoram; El-Yaniv, Ran; Luz, Kobi (2004), "Elección en línea de algoritmos de aprendizaje activo" (PDF) , J. Mach. Learn. Res. , 5 : 255–291
   • Basu, Sugato; Bilenko, Mikhail; Banerjee, Arindam; Mooney, Raymond J. (2006), "Agrupamiento probabilístico semisupervisado con restricciones", en Chapelle, Olivier; Schölkopf, Bernhard; Zien, Alexander (eds.), Aprendizaje semisupervisado , The MIT Press, págs. 73–102, doi :10.7551/mitpress/9780262033589.003.0005, ISBN 978-0-262-03358-9
   • Lima, Christiane Ferreira Lemos; Assis, Francisco M.; de Souza, Cleonilson Protásio (2011), "Un estudio comparativo del uso de la entropía de Shannon, Rényi y Tsallis para la selección de atributos en la detección de intrusiones en redes", IEEE International Workshop on Measurement and Networking, M&N 2011, Anacapri, Italia, 10 y 11 de octubre de 2011 , IEEE, págs. 77–82, doi :10.1109/IWMN.2011.6088496, S2CID  7510040
   • "Class FarthestFirst", Weka , versión 3.9.5 , Universidad de Waikato, 21 de diciembre de 2020 , consultado el 6 de noviembre de 2021 – a través de SourceForge
8. White, Douglas J. (1991), "El problema de la dispersión máxima", IMA Journal of Mathematics Applied in Business and Industry , 3 (2): 131–140 (1992), doi :10.1093/imaman/3.2.131, MR  1154657; White atribuye el uso del recorrido más lejano primero como heurística para este problema a Steuer, RE (1986), Optimización de múltiples criterios: teoría, computación y aplicaciones , Nueva York: Wiley
9. 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
10. 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, S2CID  16489402
11. Xiang, Z. (1997), "Cuantización de imágenes en color mediante la minimización de la distancia máxima entre clústeres", ACM Transactions on Graphics , 16 (3): 260–276, doi : 10.1145/256157.256159 , S2CID  17713417
12. 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, PMID  18283019
13. Mazer, E.; Ahuactzin, JM; Bessiere, P. (1998), "El algoritmo de la pista de Ariadna", Journal of Artificial Intelligence Research , 9 : 295–316, arXiv : 1105.5440 , doi : 10.1613/jair.468
14. Moenning, C.; Dodgson, NA (2003), "Un nuevo algoritmo de simplificación de nubes de puntos", 3.ª Conferencia internacional IASTED sobre visualización, obtención de imágenes y procesamiento de imágenes
15. 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, vol. 2657, págs. 483–492, doi :10.1117/12.238746, S2CID  10608234
16. Shahidi, R.; Moloney, C.; Ramponi, G. (2004), "Diseño de máscaras de puntos más lejanos para semitonos de imágenes", EURASIP Journal on Applied Signal Processing , 2004 (12): 1886–1898, Bibcode :2004EJASP2004...45S, doi : 10.1155/S1110865704403217
17. Lipman, Y.; Funkhouser, T. (2009), "Votación de Möbius para correspondencia de superficies", Proc. ACM SIGGRAPH , págs. 72:1–72:12, doi :10.1145/1576246.1531378, ISBN 978-1-60558-726-4, S2CID6001942 ​
18. Girdhar, Y.; Giguère, P.; Dudek, G. (2012), "Exploración submarina autónoma y adaptativa mediante modelado de temas en línea" (PDF) , Proc. Int. Symp. Experimental Robotics
19. Altinisik, U.; Yildirim, M.; Erkan, K. (2012), "Aislamiento de fallas de sensores no predefinidas mediante el uso del algoritmo de recorrido más lejano primero", Ind. Eng. Chem. Res. , 51 (32): 10641–10648, doi :10.1021/ie201850k
20. 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 , PMID  19085326
21. 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 , Mathematical Programming Studies, vol. 26, Springer, págs. 233–236, doi :10.1007/bfb0121103, ISBN 978-3-642-00922-8
22. Hase, Hayo (2000), "Nuevo método para la selección de sitios adicionales para la homogeneización de una distribución de puntos cosféricos no homogéneos", en Rummel, Reinhard; Drewes, Hermann; Bosch, Wolfgang; et al. (eds.), Hacia un sistema de observación geodésica global integrado (IGGOS): Simposio de la Sección II de la IAG en Múnich, 5-9 de octubre de 1998, Pósteres – Sesión B , Simposios de la Asociación Internacional de Geodesia, vol. 120, Springer, págs. 180–183, doi :10.1007/978-3-642-59745-9_35, ISBN 978-3-642-64107-7
23. 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 red de sensores incrementales eficientes" (PDF) , Proc. Simpatizante brasileño. Redes de computadoras , págs. 3-14
24. 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 de Eurographics sobre técnicas de renderizado (EGSR'07) , Aire-la-Ville, Suiza, Suiza: Asociación Eurographics, págs.277 –286, doi :10.2312/EGWR/EGSR07/277-286, ISBN 978-3-905673-52-4, Número de identificación del sujeto  18626929
25. Abbar, S.; Amer-Yahia, S.; Indyk, P.; Mahabadi, S.; Varadarajan, KR (2013), "Problema de los vecinos cercanos diversos", Actas del 29.° Simposio Anual sobre Geometría Computacional , págs. 207-214, doi :10.1145/2462356.2462401, hdl : 1721.1/87000 , ISBN 978-1-4503-2031-3, S2CID6286186 ​
26. Eppstein, David ; Har-Peled, Sariel ; Sidiropoulos, Anastasios (2020), "Agrupamiento voraz aproximado y selección de distancia para métricas de grafos", Journal of Computational Geometry , 11 (1): 629–652, doi :10.20382/jocg.v11i1a25, MR  4194877, S2CID  18316279
27. Teramoto, Sachio; Asano, Tetsuo ; Katoh, Naoki; Doerr, Benjamin (2006), "Inserción de puntos de manera uniforme en cada instancia", IEICE Transactions on Information and Systems , E89-D (8): 2348–2356, Bibcode :2006IEITI..89.2348T, doi :10.1093/ietisy/e89-d.8.2348, hdl : 2433/84849
28. 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