Variations on Zombies and Survivor in Simple Polygons
Public Deposited- Resource Type
- Creator
- Abstract
We study the pursuit-evasion game of a zombie and a survivor on point visibility graphs of simple polygons. A zombie has one objective: catch a survivor by occupying the vertex occupied by the survivor. On its turn, a zombie can only move on the first edge of a \textit{geodesic} path to the survivor's location. A survivor may choose to move to any vertex adjacent to its current vertex; the objective of the survivor is to survive as long as possible. Both players take turns and have complete information of the graph and each others' position. We consider two variants played on point visibility graphs: the case where edges have Euclidean weight between their endpoints, and the case where all edge weights are one; we denote these graphs as $PVG_D(P)$, and $PVG(P)$ respectively. We show that $PVG_D(P)$ is a zombie-win graph, and for any spiral polygon $P_s$, $PVG(P_s)$ is a zombie-win graph.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2022 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2022
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
blackman-variationsonzombiesandsurvivorinsimplepolygons.pdf | 2023-05-05 | Public | Download |