Straight Line Movement in Morphing and Pursuit Evasion

Pursuit Evasion;Cops and Robbers;Visibility Graphs;Morphing

Vosoughpour Yazdchi, Hamidehaffiliation1:Faculty of Mathematics ; advisor:Lubiw, Anna ; Lubiw, Anna ;

University of Waterloo

关键词: Visibility Graphs;    Cops and Robbers;    Pursuit Evasion;    Morphing;    Doctoral Thesis;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/12581/3/VosoughpourYazdchi_Hamideh.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Piece-wise linear structures are widely used to define problems and to represent simplifiedsolutions in computational geometry. A piece-wise linear structure consists of straight-lineor linear pieces connected together in a continuous geometric environment like 2D or 3DEuclidean spaces. In this thesis two different problems both with the approach of findingpiece-wise linear solutions in 2D space are defined and studied: straight-line pursuit evasionand straight-line morphing.Straight-line pursuit evasion is a geometric version of the famous cops and robbers gamethat is defined in this thesis for the first time. The game is played in a simply connectedregion in 2D. It is a full information game where the players take turns. The cop’s goalis to catch the robber. In a turn, each player may move any distance along a straightline as long as the line segment connecting their current location to the new location isnot blocked by the region’s boundary. We first prove that the cop can always win thegame when the players move on the visibility graph of a simple polygon. We prove this byshowing that the visibility graph of a simple polygon is ;;dismantlable” (the known class ofcop-win graphs). Polygon visibility graphs are also shown to be 2-dismantlable. Two othersettings of the game are also studied in this thesis: when the players are free to move onthe infinitely many points inside a simple polygon, and inside a splinegon. In both caseswe show that the cop can always win the game. For the case of polygons, the proposed copstrategy gives an asymptotically tight linear bound on the number of steps the cop needsto catch the robber. For the case of splinegons, the cop may need a quadratic number ofsteps with the proposed strategy, while our best lower bound is linear.Straight-line morphing is a type of morphing first defined in this thesis that provides anice and smooth transformation between straight-line graph drawings in 2D. In straight-line morphing, each vertex of the graph moves forward along the line segment connectingits initial position to its final position. The vertex trajectories in straight-line morphingare very simple, but because the speed of each vertex may vary, straight-line morphs aremore general than the commonly used ;;linear morphs” where each vertex moves at uniformspeed. We explore the problem of whether an initial planar straight-line drawing of a graphcan be morphed to a final straight-line drawing of the graph using a straight-line morphthat preserves planarity at all times. We prove that this problem is NP-hard even forthe special case where the graph drawing consists of disjoint segments. We then look atsome restricted versions of the straight-line morphing: when only one vertex moves at atime, when the vertices move one by one to their final positions uninterruptedly, and whenthe edges morph one by one to their final configurations in the case of disjoint segments.Some of the variations are shown to be still NP-complete while some others are solvablein polynomial time. We conjecture that the class of planar straight-line morphs is aspowerful as the class of planar piece-wise linear straight-line morphs. We also explorea simpler problem where for each edge the quadrilateral formed by its initial and finalpositions together with the trajectories of its two vertices is convex. There is a necessarycondition for this case that we conjecture is also sufficient for paths and cycles.