{"id":{"repo_id":"carleton","oai_identifier":"oai:carleton.scholaris.ca:20.500.14718/42717"},"canonical_url":"https://search.dev.ndltd.org/etd/carleton/oai:carleton.scholaris.ca:20.500.14718/42717","repository":{"repo_id":"carleton","name":"Carleton University","base_url":"https://carleton.scholaris.ca/server/oai/request"},"display":{"title":"Variations on Zombies and Survivor in Simple Polygons","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&apos;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&apos; 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.","abstract_html":"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&amp;apos;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&amp;apos; 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 <span class=\"etd-inline-math\">PVG<sub>D</sub>(P)</span>, and $PVG(P)$ respectively. We show that <span class=\"etd-inline-math\">PVG<sub>D</sub>(P)</span> is a zombie-win graph, and for any spiral polygon <span class=\"etd-inline-math\">P<sub>s</sub></span>, <span class=\"etd-inline-math\">PVG(P<sub>s</sub>)</span> is a zombie-win graph.","abstract_has_math":true,"creators":["Blackman, Christopher Paul"],"institution":"Carleton University","degree_name":"Master of Computer Science (M.C.S.)","degree_level":"Master&apos;s","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-07-24T01:34:43Z","subjects":[],"languages":["en"],"rights":["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."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.22215/etd/2022-15130"],"render_values":[{"text":"10.22215/etd/2022-15130","href":"https://doi.org/10.22215/etd/2022-15130","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14718/42717","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Blackman, Christopher Paul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-04-08T20:42:47Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-04-08T20:42:47Z"]},{"key":"dc:date.issued","label":"Date","values":["2022"]},{"key":"dc:publisher","label":"Institution","values":["Carleton University"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master&apos;s"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Computer Science (M.C.S.)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.22215/etd/2022-15130"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14718/42717"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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&apos;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&apos; 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."]},{"key":"dc:title","label":"Title","values":["Variations on Zombies and Survivor in Simple Polygons"]}]}],"canonical_facts":{"dc:creator":["Blackman, Christopher Paul"],"dc:date.accessioned":["2025-04-08T20:42:47Z"],"dc:date.available":["2025-04-08T20:42:47Z"],"dc:date.issued":["2022"],"dc:description.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&apos;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&apos; 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."],"dc:identifier.doi":["10.22215/etd/2022-15130"],"dc:identifier.uri":["https://hdl.handle.net/20.500.14718/42717"],"dc:language.iso":["en"],"dc:publisher":["Carleton University"],"dc:rights":["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."],"dc:title":["Variations on Zombies and Survivor in Simple Polygons"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Master&apos;s"],"thesis:degree_name":["Master of Computer Science (M.C.S.)"]},"updated_at":"2026-07-24T01:34:43Z"}