Problema de ruta del vigilante

El problema del vigilante es un problema de optimización en geometría computacional cuyo objetivo es calcular la ruta más corta que un vigilante debe seguir para proteger un área completa con obstáculos, dado únicamente un mapa del área. El desafío consiste en asegurar que el vigilante mire detrás de cada esquina y determinar el mejor orden en el que debe visitar las esquinas. El problema puede resolverse en tiempo polinomial cuando el área a proteger es un polígono simple . ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} El problema es NP-difícil para polígonos con agujeros , ^{[ 1 ]} pero puede aproximarse en tiempo polinomial mediante una solución cuya longitud está dentro de un factor polilogarítmico de la óptima. ^{[ 4 ]}

Véase también

Problema de la galería de arte , que implica igualmente observar todos los puntos de un área determinada, pero con múltiples vigilantes fijos.

Referencias

1 2 Chin, Wei-Pang; Ntafos, Simeon (1988), "Optimum watchman routes", Information Processing Letters , 28 (1): 39– 44, doi : 10.1016/0020-0190(88)90141-X , MR 0947253 .
↑ Carlsson, S.; Jonsson, H.; Nilsson, BJ (1999), "Encontrar la ruta más corta para el vigilante en un polígono simple", Geometría discreta y computacional , 22 (3): 377– 402, doi : 10.1007/PL00009467 , MR 1706598 .
↑ Tan, Xuehou (2001), "Cálculo rápido de las rutas más cortas de vigilancia en polígonos simples", Information Processing Letters , 77 (1): 27–33 , doi : 10.1016/S0020-0190(00)00146-0 , MR 1813864 .
↑ Mitchell, Joseph SB (2013), "Aproximación de rutas de vigilancia", Actas del Vigésimo Cuarto Simposio Anual ACM–SIAM sobre Algoritmos Discretos (SODA '13) , SIAM, págs. 844–855 , doi : 10.1137/1.9781611973105.60 , ISBN 978-1-611972-51-1.

[cn88-1] 1 2 Chin, Wei-Pang; Ntafos, Simeon (1988), "Optimum watchman routes", Information Processing Letters , 28 (1): 39– 44, doi : 10.1016/0020-0190(88)90141-X , MR 0947253 .

[2] Carlsson, S.; Jonsson, H.; Nilsson, BJ (1999), "Encontrar la ruta más corta para el vigilante en un polígono simple", Geometría discreta y computacional , 22 (3): 377– 402, doi : 10.1007/PL00009467 , MR 1706598 .

[3] Tan, Xuehou (2001), "Cálculo rápido de las rutas más cortas de vigilancia en polígonos simples", Information Processing Letters , 77 (1): 27–33 , doi : 10.1016/S0020-0190(00)00146-0 , MR 1813864 .

[4] Mitchell, Joseph SB (2013), "Aproximación de rutas de vigilancia", Actas del Vigésimo Cuarto Simposio Anual ACM–SIAM sobre Algoritmos Discretos (SODA '13) , SIAM, págs. 844–855 , doi : 10.1137/1.9781611973105.60 , ISBN 978-1-611972-51-1.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]