Title

Line-of-Sight Pursuit and Evasion Games on Polytopes in R^n

Graduation Year

2016

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Second Department

Computer Science

Reader 1

Ran Libeskind-Hadas

Reader 2

Nicholas Pippenger

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2016 John E Phillpot

Abstract

We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rn, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be Pursuer-win and those known not to be remains an problem for future researchers.