# Variations on Zombies and Survivor in Simple Polygons

## Creator:

Blackman, Christopher Paul

2022

## 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.

Computer science
Game theory

English

## Publisher:

Carleton University

## Thesis Degree Name:

Master of Computer Science:
M.C.S.

Master's

Computer Science

## Parent Collection:

Theses and Dissertations