Bounds for Cops and Robber Pursuit

Laurent Alonso 1 Edward M. Reingold 2
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We prove that the robber can evade (that is, stay at least unit distance from) at least $\lfloor n/5.889 \rfloor$ cops patroling an $n \times n$ continuous square region, that a robber can always evade a single cop patroling a square with side length $4$ or larger, and that a single cop on patrol can always capture the robber in a square with side length smaller than $2.189\cdots$.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2010, 43 (9), pp.749-766. 〈10.1016/j.comgeo.2010.02.002〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00459460
Contributeur : Laurent Alonso <>
Soumis le : mercredi 24 février 2010 - 09:26:24
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Bounds for Cops and Robber Pursuit. Computational Geometry, Elsevier, 2010, 43 (9), pp.749-766. 〈10.1016/j.comgeo.2010.02.002〉. 〈inria-00459460〉

Partager

Métriques

Consultations de la notice

203