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

Author

John Phillpot, Harvey Mudd CollegeFollow

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 Rⁿ, 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.

Recommended Citation

Phillpot, John, "Line-of-Sight Pursuit and Evasion Games on Polytopes in R^n" (2016). HMC Senior Theses. 80.
https://scholarship.claremont.edu/hmc_theses/80

Source Fulltext

https://www.math.hmc.edu/~jphillpot/thesis/