Variations on Zombies and Survivor in Simple Polygons

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Blackman, Christopher Paul

Date: 

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.

Subject: 

Computer science
Game theory

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).