Lower Bounds for Cops and Robber Pursuit (PDF; 32 pages)

By Laurent Alonso and Edward M. Reingold

submitted for publication.

We prove that the robber can evade (that is, stay at least unit distance from) at least lfloor n/5.889 rfloor cops in an n by n continuous square region, that a robber can always evade a single cop in a square with side length 4.5, and that a single cop can always capture the robber in a square with side length smaller than 2.189... . We also make many new observations and conjectures about both the continuous problem and the discrete problem in which a robber tries to evade k cops on an n by n grid.

Slides (PDF; 37 pages)

Determining Plurality (PDF; 19 pages)

By Laurent Alonso and Edward M. Reingold

ACM Transactions on Algorithms , to appear.

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that (c-1)(n-c)/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775 c + 3.6)n + O(c^2) color comparisons for c >= 9.

Slides (PDF; 36 pages)

Average-Case Analysis of Some Plurality Algorithms (PDF; 35 pages)

By Laurent Alonso and Edward M. Reingold

ACM Transactions on Algorithms , to appear.

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the c^n colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is (c^2 + c - 2)n/(2c) - O(c^2). We present and analyze an algorithm for the case c=3 colors whose average complexity on the 3^n equally probable inputs is 7083n/5425 + O(sqrt n) = 1.3056...n + O(sqrt n), substantially better than the expected complexity 5n/3 + O(1) = 1.6666...n + O(1) of the obvious algorithm. We describe a similar algorithm for c=4 colors whose average complexity on the 4^n equally probable inputs is 761311n/402850 + O(log n)= 1.8898...n + O(log n), substantially better than the expected complexity 9n/4 + O(1) = 2.25n + O(1) of the obvious algorithm.

Average-Case Lower Bounds for the Plurality Problem (PDF; 19 pages)

By Laurent Alonso and Edward M. Reingold

ACM Transactions on Algorithms , to appear.

Given a set of n elements, each of which is colored one of c >= 2 colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the c^n colorings are equally probable. We prove a general lower bound of cn/3 - O(sqrt n) for c >= 2; we prove the stronger particular bounds of 7n/6 - O(sqrt n) for c = 3, 54n/35 - O(sqrt n) for c = 4, 607n/315 - O(sqrt n) for c = 5, 1592n/693 - O(sqrt n) for c = 6, 7985n/3003 - O(sqrt n) for c = 7, and 19402n/6435 n - O(sqrt n) for c = 8.

Slides (PDF; 58 pages)

Back to Edward Reingold's Homepage