El problema del vigilante es un problema de optimización en geometría computacional donde el objetivo es calcular la ruta más corta que un vigilante debe tomar para proteger un área completa con obstáculos dado solo un mapa del área. El desafío es asegurarse de que el vigilante mire detrás de cada esquina y determinar el mejor orden en el que se deben visitar las esquinas. El problema se puede resolver 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 por una solución cuya longitud está dentro de un factor polilogarítmico de óptimo. [4]
Ver también
- Problema de la galería de arte , que también implica ver todos los puntos de un área determinada, pero con varios vigilantes estacionarios
Referencias
- ^ a b 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 de vigilancia más corta 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 de vigilancia más cortas 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.