Improved 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 n cops can capture (that is, some cop can get less than unit distance from) a robber in a continuous square region with side length less than sqrt(5)n and hence that [n/sqrt(5)]+1 cops can capture a robber in a square with side length n. We extend these results to three dimensions, proving that 0.34869...n^2+O(n) cops can capture a robber in an nxnxn cube and that a robber can forever evade fewer than 0.02168...n^2+O(n) cops in that cube.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2011, 44 (8), pp.365-369. 〈10.1016/j.comgeo.2011.03.001〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00756031
Contributeur : Laurent Alonso <>
Soumis le : jeudi 22 novembre 2012 - 13:34:18
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18

Lien texte intégral

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Improved bounds for cops-and-robber pursuit. Computational Geometry, Elsevier, 2011, 44 (8), pp.365-369. 〈10.1016/j.comgeo.2011.03.001〉. 〈hal-00756031〉

Partager

Métriques

Consultations de la notice

208