<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T11:04:23Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/3964" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/3964</identifier><datestamp>2017-03-21T16:58:34Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="4ee2fab7-0370-4538-9672-9174a7b83e3f" confidence="600">Bahun, Stephen</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-09-10T16:27:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2008-09-10T16:27:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-09-10T16:27:11Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2008</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/3964</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In the area of motion planning, considerable work has been done on guarding&#xd;
problems, where &amp;quot;guards&amp;quot;, modelled as points, must guard a polygonal&#xd;
space from &amp;quot;intruders&amp;quot;. Different variants&#xd;
of this problem involve varying a number of factors. The guards performing &#xd;
the search may vary in terms of their number, their mobility, and their&#xd;
range of vision. The model of intruders may or may not allow them to &#xd;
move. The polygon being searched may have a specified starting point,&#xd;
a specified ending point, or neither of these. The typical question asked&#xd;
about one of these problems is whether or not certain polygons can be&#xd;
searched under a particular guarding paradigm defined by the types&#xd;
of guards and intruders.&#xd;
&#xd;
In this thesis, we focus on two cases of a chain of guards searching&#xd;
a room (polygon with a specific starting point) for mobile intruders.&#xd;
The intruders must never be allowed to escape through the door undetected.&#xd;
In the case of the two guard problem, the guards must start at the door &#xd;
point and move in opposite directions along the boundary of the &#xd;
polygon, never crossing the door point. At all times, the&#xd;
guards must be able to see each other. The search is complete once both&#xd;
guards occupy the same spot elsewhere on the polygon. In the case of&#xd;
a chain of three guards, consecutive guards in the chain must always&#xd;
be visible. Again, the search starts at the door point, and the outer&#xd;
guards of the chain must move from the door in opposite directions. &#xd;
These outer guards must always remain on the boundary of the polygon.&#xd;
The search is complete once the chain lies entirely on a portion of &#xd;
the polygon boundary not containing the door point.&#xd;
&#xd;
Determining whether a polygon can be searched is a problem in the area &#xd;
of visibility in polygons; further to that, our work is related&#xd;
to the area of planning algorithms. We look for ways to find optimal schedules that minimize&#xd;
the distance or time required to complete the search. This is done&#xd;
by finding shortest paths in visibility diagrams that indicate valid &#xd;
positions for the guards. In the case of&#xd;
the two-guard room search, we are able to find the shortest distance&#xd;
schedule and the quickest schedule. The shortest distance schedule&#xd;
is found in O(n^2) time by solving an L_1 shortest path problem &#xd;
among curved obstacles in two dimensions. The quickest search schedule is &#xd;
found in O(n^4) time by solving an L_infinity shortest path&#xd;
problem among curved obstacles in two dimensions.&#xd;
For the chain of three guards, a search schedule minimizing the total&#xd;
distance travelled by the outer guards is found in O(n^6) time by&#xd;
solving an L_1 shortest path problem among curved obstacles in two dimensions.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">computational geometry</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">visibility</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Algorithms for Optimizing Search Schedules in a Polygon</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>