<?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-22T19:57:56Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/12581" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/12581</identifier><datestamp>2025-03-26T23:36:12Z</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="advisor">Lubiw, Anna</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="e9995ab4-c66b-40a1-b43e-08b65f103ca5" confidence="600">Vosoughpour Yazdchi, Hamideh</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2017-10-24T16:32:22Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2017-10-24T16:32:22Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2017-10-24</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2017-10-06</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/12581</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Piece-wise linear structures are widely used to define problems and to represent simplified&#xd;
solutions in computational geometry. A piece-wise linear structure consists of straight-line&#xd;
or linear pieces connected together in a continuous geometric environment like 2D or 3D&#xd;
Euclidean spaces. In this thesis two different problems both with the approach of finding&#xd;
piece-wise linear solutions in 2D space are defined and studied: straight-line pursuit evasion&#xd;
and straight-line morphing.&#xd;
Straight-line pursuit evasion is a geometric version of the famous cops and robbers game&#xd;
that is defined in this thesis for the first time. The game is played in a simply connected&#xd;
region in 2D. It is a full information game where the players take turns. The cop’s goal&#xd;
is to catch the robber. In a turn, each player may move any distance along a straight&#xd;
line as long as the line segment connecting their current location to the new location is&#xd;
not blocked by the region’s boundary. We first prove that the cop can always win the&#xd;
game when the players move on the visibility graph of a simple polygon. We prove this by&#xd;
showing that the visibility graph of a simple polygon is “dismantlable” (the known class of&#xd;
cop-win graphs). Polygon visibility graphs are also shown to be 2-dismantlable. Two other&#xd;
settings of the game are also studied in this thesis: when the players are free to move on&#xd;
the infinitely many points inside a simple polygon, and inside a splinegon. In both cases&#xd;
we show that the cop can always win the game. For the case of polygons, the proposed cop&#xd;
strategy gives an asymptotically tight linear bound on the number of steps the cop needs&#xd;
to catch the robber. For the case of splinegons, the cop may need a quadratic number of&#xd;
steps with the proposed strategy, while our best lower bound is linear.&#xd;
Straight-line morphing is a type of morphing first defined in this thesis that provides a&#xd;
nice and smooth transformation between straight-line graph drawings in 2D. In straight-&#xd;
line morphing, each vertex of the graph moves forward along the line segment connecting&#xd;
its initial position to its final position. The vertex trajectories in straight-line morphing&#xd;
are very simple, but because the speed of each vertex may vary, straight-line morphs are&#xd;
more general than the commonly used “linear morphs” where each vertex moves at uniform&#xd;
speed. We explore the problem of whether an initial planar straight-line drawing of a graph&#xd;
can be morphed to a final straight-line drawing of the graph using a straight-line morph&#xd;
that preserves planarity at all times. We prove that this problem is NP-hard even for&#xd;
the special case where the graph drawing consists of disjoint segments. We then look at&#xd;
some restricted versions of the straight-line morphing: when only one vertex moves at a&#xd;
time, when the vertices move one by one to their final positions uninterruptedly, and when&#xd;
the edges morph one by one to their final configurations in the case of disjoint segments.&#xd;
Some of the variations are shown to be still NP-complete while some others are solvable&#xd;
in polynomial time. We conjecture that the class of planar straight-line morphs is as&#xd;
powerful as the class of planar piece-wise linear straight-line morphs. We also explore&#xd;
a simpler problem where for each edge the quadrilateral formed by its initial and final&#xd;
positions together with the trajectories of its two vertices is convex. There is a necessary&#xd;
condition for this case that we conjecture is also sufficient for paths and cycles.</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">Pursuit Evasion</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Cops and Robbers</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Visibility Graphs</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Morphing</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Straight Line Movement in Morphing and Pursuit Evasion</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Lubiw, Anna</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</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>