Improved bounds for cops-and-robber pursuit

摘要

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 5n and hence that ?n/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?~(n2)+O(n) cops can capture a robber in an n×n×n cube and that a robber can forever evade fewer than 0.02168?~(n2)+O(n) cops in that cube.