Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Clarkson, Kyle P.
Master of Science - MSc
University of British Columbia
In this thesis we consider the problem faced by an agent who is tasked with inspecting certain objects within the plane. In particular, given some starting position not interior to a convex polygon the agent must traverse through the plane to fully see all edges of the polygon. However traversal is expensive for the agent and so the agent would like to determine the shortest path it can take such that all edges of the polygon will be seen from the path. For all polygons and feasible starting positions we present an efficient algorithm for determining what the shortest path is by characterizing properties that any such path must exhibit. Next we consider how the agent should accomplish this task when it is only aware that the polygon it is to inspect is convex, but not its shape (i.e. location of edges.) In such a scenario the agent must search for the edges by traversing through the plane. Yet if such searching is not done in an efficient manner, the distance traversed may be unacceptably large with respect to the length of the optimal path. We discuss several strategies that the agent can employ that will ensure that the distance it traverses to see all edges is at most a constant times the length of the optimal path.
On Competitive Strategies for External Exploration of aConvex PolygonbyKyle P. ClarksonBSc (Hons), Brandon University, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)December 2020c© Kyle P. Clarkson, 2020The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:On Competitive Strategies for External Exploration of a Convex Poly-gonsubmitted by Kyle P. Clarkson in partial fulfillment of the requirements for thedegree of Master of Science in Computer Science.Examining Committee:Dr. Will Evans, Computer ScienceSupervisorDr. Nick Harvey, Computer ScienceSupervisory Committee MemberiiAbstractIn this thesis we consider the problem faced by an agent who is tasked with inspect-ing certain objects within the plane. In particular, given some starting position notinterior to a convex polygon the agent must traverse through the plane to fully seeall edges of the polygon. However traversal is expensive for the agent and so theagent would like to determine the shortest path it can take such that all edges ofthe polygon will be seen from the path. For all polygons and feasible starting posi-tions we present an efficient algorithm for determining what the shortest path is bycharacterizing properties that any such path must exhibit.Next we consider how the agent should accomplish this task when it is onlyaware that the polygon it is to inspect is convex, but not its shape (i.e. location ofedges.) In such a scenario the agent must search for the edges by traversing throughthe plane. Yet if such searching is not done in an efficient manner, the distancetraversed may be unacceptably large with respect to the length of the optimal path.We discuss several strategies that the agent can employ that will ensure that thedistance it traverses to see all edges is at most a constant times the length of theoptimal path.iiiLay SummaryGiven a convex, polygonal object in the plane a mobile agent is tasked with seeingall sides of the object. This thesis explores what is the shortest route the agentcan take from any starting position to achieve this goal. Further it considers howthe agent should examine the object when the location of its edges is not knownin advance such that the length of the resulting path is close to the length of theshortest possible path. This thesis presents several efficient techniques for the agentto employ to solve both of these tasks which are improvements on recent work byTiktinsky and others [22].ivPrefaceThe work presented in this thesis was conducted by me at the Algorithms Lab inthe faculty of computer science at the University of British Columbia, with theassistance of my supervisor Will Evans.The research topic resulted from conversations with Will about problems per-taining to mobile agents with a given task, particularly those in the online settingas described in Chapter 4. The insights discussed in this thesis are greatly indebtedto previous work on competitive strategies for searching in the plane and look-ing around corners, such as those by Baeza-Yates et al. [2] and Icking et al. [16]respectively.Portions of the work in Chapter 4 have been published at the 32nd CanadianConference on Computational Geometry (2020) titled as ”External Exploration ofa Convex Polygon” by ”Kyle Clarkson and Will Evans”.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 The Convex Polygon Inspection Problem . . . . . . . . . . . . . . . 113.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Properties of a Shortest Inspection Path . . . . . . . . . . . . . . 123.3 A Linear Time Algorithm . . . . . . . . . . . . . . . . . . . . . . 183.4 Extension: A Specified Termination Point . . . . . . . . . . . . . 273.5 Extension: Constraints on Inspection Angle . . . . . . . . . . . . 294 The Online Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.1 The Convex Chain Inspection Problem . . . . . . . . . . . . . . . 384.2 A Two-Sided Search Strategy . . . . . . . . . . . . . . . . . . . . 43vi4.3 The Angle Hull Strategy . . . . . . . . . . . . . . . . . . . . . . 474.4 A Lower Bound on the Length of the Shortest Inspection Path . . 524.5 Extension: Constraints on Inspection Angle . . . . . . . . . . . . 545 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62viiList of FiguresFigure 2.1 An instance of the art galley problem with n = 12 vertices and4 ”teeth” whose existence requires at least 4 guards to com-pletely guard the polygon. By triangulating the polygon, alledges are seen by placing 4 guards at the red vertices. . . . . . 4Figure 3.1 A path may contact an edge extension in one of three ways.Note for a tangential contact the path may or may not enterthe half-space (whose boundary is the edge extension) aftertraversing along the edge extension. . . . . . . . . . . . . . . 13Figure 3.2 Proof of Lemma 3.2.1. In blue are the two disconnect sub-chains of the boundary seen from the the path in red. As thepath cannot traverse through the polygon, other edges must beseen from the path that connects the two chains. . . . . . . . 15Figure 3.3 Proof of Theorem 3.2.3. The first reflecting contact at v1 of theblue path P can be removed to construct the red path P ∗ thatmoves from s to the reflecting contact at v2. The edge that isseen at v1 on the blue path is now seen by a crossing contacton the red path. The chain of edges C = {e1, e2, e3, e4} seenfrom P [s, v2] is a subset of the chain C ′ = {e1, e2, e3, e4, e5}seen from P ∗[v2, w]. . . . . . . . . . . . . . . . . . . . . . . 17viiiFigure 3.4 The jump-off vertices and their projections onto respective edgeextensions for an agent traversing in the counterclockwise di-rection around the boundary of Q. Labelled are the verticesw4ccw, w5ccw, and w6ccw along with their projections onto h4, h5,and h6 respectively. . . . . . . . . . . . . . . . . . . . . . . . 21Figure 3.5 A shortest inspection path which does not contact the boundaryofQ. The location of pi (which dictates the location of ti) is thedistance d tan(θi) from the projection of s onto hi−1 towardsthe endpoint of ei−1 resulting from the solution of setting thederivative of the path’s length to zero. The path is feasible asti is not located between the projections of wicw and wiccw ontohi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 3.6 As the projection of s onto hi−1 is contained in between theprojections of wi−1ccw and wi−1cw onto hi−1 the shortest inspec-tion path contacts the boundary of the polygon before reachinghi−1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23Figure 3.7 Determining where the inspection path makes contact with hi−1before contacting ∂Q. Edges e1, e2, e3, and e4 are candidateedges for the bounce-operation, and subpaths that reach eachrespective edge extension are shown. In red is the shortestinpsection path that makes a reflecting contact on h4, thenmoves to h5. . . . . . . . . . . . . . . . . . . . . . . . . . . 24Figure 3.8 By triangle inequality, the path spq∗ + pq∗q∗ will be shorterthan spq + pqq + qq∗ . . . . . . . . . . . . . . . . . . . . . 25Figure 3.9 Proof of Theorem 3.4.1. A shortest inspection path that doesnot complete inspection upon making a second reflecting con-tact can be shortened to an inspection path with only one re-flecting contact. . . . . . . . . . . . . . . . . . . . . . . . . 29ixFigure 3.11 The case when edge ei on which x lies is not seen from s. Inblue is the shortest inspection path that sees x by making a re-flecting contact at p on IRiR(x) and ends at t. This path crossesIRi−1R (v) twice at points b and c. In red is a shorter inspectionpath which makes a reflecting contact with IRi−1R (v) at pointa and ends at t. . . . . . . . . . . . . . . . . . . . . . . . . . 34Figure 4.1 Two instances of looking around a single corner where the op-timal path (in red) either moves away from the boundary orfollows the boundary. In blue is the path which follows a cir-cular arc centered at the corner with radius the distance s isaway from the corner. . . . . . . . . . . . . . . . . . . . . . 39Figure 4.2 An instance of the corner-radius problem. In red is the opti-mal path from s that sees all edges and blue is the path re-sulting from the corner-radius strategy. Note that the optimalpath leaves the boundary at the vertex shared by e2 and e3; thissubpath consists of two right triangle base lengths. . . . . . . 42Figure 4.3 The starting position is off of the boundary of chain. The orig-inal chain with initially seen edges are grayed out and the newchain starting at s consists of three edges. The optimal pathand path generated by the corner-radius strategy are the samefor both chains. . . . . . . . . . . . . . . . . . . . . . . . . . 43Figure 4.4 The angle hull of a convex polygon shown in red. For all pointsp on the convex hull, the two rays from p to the furthest seenvertices of the polygon form a right angle. . . . . . . . . . . . 48Figure 4.5 An instance of the angle hull strategy. The agent on arc a2sees both endpoints of the subchain formed by edges e1 ande2. The circle center in which arc ai is generated from is across labelled ci. The angles α3 and α4 correspond to the an-gles given by the light green and dark green shaded regions,and α5 and α6 the light purple and dark purple shaded regionsrespectively. Note that A3 +A4 = φ3 + φ4 and A4 = φ4. . . 50xFigure 4.6 A three edge polygon in which the agent, following some strat-egy, takes an initial step in the wrong direction from s to a, thenreturns to s. The agent then moves in the correct direction toinspect the final edge. In red is the shortest inspection pathwith length  which can be arbitrary small for such polygons. . 52Figure 4.7 Three rays through p1 = a, p2, and p3 = b. For each ray, thelines parallel to the ray are shown as dash dotted lines. . . . . 54Figure 4.8 In blue is the inspection path resulting from the perpendiculartraversal strategy with lengths ai and bi labelled. In red is theshortest inspection path for this chain. Notice the collection ofright triangles formed with base lengths of O. . . . . . . . . . 56xiAcknowledgmentsForemost I would like to give thanks to my supervisor Will Evans. His advice,suggestions, and support provided clarity, guidance, and reassurance in the hec-tic moments that together compose a master’s program. I could not have done itwithout you.Of course nothing could ever replace the love and support of those that preparedme to take on this endeavour. To my niece Aaliyah, sister Kendall, mother andfather Kim and Kelvin, grandparents Vivian and Robert, Mona and Keith, and allof my uncles, aunties, cousins, relations, mentors, teachers, coaches, peers, andfriends, thank you for your unwavering belief that I could complete such a feat. Itwas your love and support that carried me through all the moments of doubt andfear. Thank you.And finally, thank you to all the individuals and organizations that assisted infinancially supporting me throughout my education. One does not need a master’sdegree to know the value of love from those closest to you, yet such an individualalso knows that many doors cannot be opened with love alone. Your contributionsto not only me but to many other students is the key to open that door. In particularI give thanks to Pine Creek First Nation who has supported me through my timeboth as an undergraduate and a master’s student. Meegwetch.xiiChapter 1IntroductionProblems that involve a notion of visibility by mobile agents are well-known inareas of research such as computational geometry and robotics. From the moretheoretical aspect where agents can be modelled as infinitely small points in theplane equipped with perfect sensors and control inputs, to the more applied domainwhere agents rely on many complex actuators for movement and imperfect sensorreadings to accomplish tasks given to them.We consider a problem from the former domain: consider a point agent that istasked with traversing through the plane to inspect the exterior edges of a convexpolygon. From its current location p, the agent can see any point q in the plane ifthe line segment pq does not intersect any obstacle (i.e. the polygon itself.)Given some starting position and the location of the polygon, the problem facedby the agent is to determine what is the shortest path exterior to the polygon thatallows the agent to see all edges. In this work we present an efficient algorithmthat the agent can employ to determine such a path whose correctness follows byan analysis of the properties any shortest path must satisfy. We also consider anextension of this problem where visibility of a point of an edge requires the agentto be viewing it at a sufficiently large incident angle (i.e. the agent cannot see allpoints of an edge where the line of sight is near-parallel with the edge.)While we can determine the shortest path that allows the agent to inspect alledges when the shape and location of the polygon is known in advance, one won-ders how the agent should go about its inspection task when this knowledge is1only obtained by seeing points on the polygon. We define several strategies for theagent to employ such that for all convex polygons and feasible starting positions,the length of the resulting path is at most a constant times the length of the shortestinspection path that the agent could have taken.The work presented in this thesis is an improvement on recent work by Tikin-sky et al. [22]. Our work is largely built upon previous research pertaining tocompetitive analysis of online algorithms. In particular, we build upon strategiespresented by Icking et al. [16] for optimally looking around a single corner tolooking around several corners, as well as work by several researchers on the m-lane cow path problem, where m = 2, to competitively explore in both directionsaround the polygon.2Chapter 2Related WorkVisibility problems are a core component computational geometry. Perhaps theoldest and most well-known of which is the art gallery problem first proposed byKlee nearly half a century ago [19]. Given the floor plans of a planar art gallery,the question is how many stationary point-guards are required, along with theirpositions, such that all walls of the art gallery are fully seen? By describing thebuilding’s layout as the interior of a simple polygon in the the plane with guardsallowed to be positioned along the gallery’s walls (i.e. on the boundary of thepolygon) the problem can be stated as a decision problem: does there exists aplacement of at most k guards such that all walls of the polygon are seen by atleast one guard? While it has long been known that even if guards are restrictedto being located at vertices of the polygons, asking for the minimum number ofguards needed is NP-Hard [17, 20] even for one polygon, it wasn’t until 2018that Abrahamsen et al. showed that the art gallery problem is complete for theexistential theory of the reals [1].Despite these results, for n vertices of the polygon bn/3c guards are sufficientand sometimes necessary to guard the entirety of the polygon. A short, elegantproof of this was shown by Fisk [10] in which the polygon is triangulated (withoutadding vertices) and 3-coloured. Then by placing guards on the vertices corre-sponding to one of the three colours, the guards can see the boundaries of thetriangles, some of which are edges of the polygon. As these triangles partition thefloor space of the polygon, seeing the boundaries of all triangles sees all edges of3Figure 2.1: An instance of the art galley problem with n = 12 vertices and 4”teeth” whose existence requires at least 4 guards to completely guardthe polygon. By triangulating the polygon, all edges are seen by placing4 guards at the red vertices.the polygon; see Figure 2.1. While most problems that are similar to the art galleryproblem consider guarding the interior of an object, the equivalent problem wherethe exterior of an object is to be guarded is known as the fortress problem. Both ofthese are discussed in O’Rourke’s book on variants of the art gallery problem [19].A natural generalization of the art gallery problem is to enable the guards withthe ability to traverse through the polygon. Here, we only require that all walls ofthe art gallery are to be seen from some position on any of the paths taken by aguard. Relevant to this work is when only one guard is burdened with monitor-ing the gallery and is called the watchman route problem. In this scenario, oneis usually interested in determining what is the shortest route (cycle) inside of thepolygon such that all the points of the polygon are seen from some point along thepath. This problem was first considered by Chin and Ntafos [4, 5] in 1986. In theseworks the authors gave efficient algorithms for determining the shortest watchmanroute for specific types of polygons such as rectilinear polygons. For general poly-gons with n edges a O(n4) time algorithm was proposed by the authors, howeverit was later observed that their algorithm contained flaws [8]. Despite these issuesthe ground work was set for methods to tackle the watchman route problem. Thekey idea is not to ask in what positions does the watchman see an edge, but ratherwhat area of the plane can an edge be seen from. Indeed, for each edge there is a4region of space, uninhibited by any obstacles, which the agent must enter to see theedge. Clearly any watchman route must reach all of these areas to see the entiretyof the polygon. So to determine what is the shortest watchman route, one can askthe question: what is the shortest route that reaches all of these areas.Other researchers presented their own solutions, as well as attempted to resolvethe earlier errors mentioned above. In 1993 Tan et al. provided a solution that itselfcontained errors. It wasn’t until 1999 that Tan et al. [21] gave a correct dynamicprogramming based algorithm to find the shortest watchman route in O(n4) time.An algorithm with an improved runtime ofO(n3 log n) was given by Dror et al. [8]where the authors considered a more general problem, the touring polygons prob-lem, in which given starting and ending positions s and t, an agent must determinethe shortest s − t path that visits a sequence of polygons in the plane, given someordering of the polygons. The authors observed that the watchman route problemis really a special instance of the general touring polygons problem. Indeed asmentioned above each edge has a region of space in which the agent can see theedge. For each polygon its structure will give rise to essential areas, edges whichhave a small, bounded area from which they can be seen (e.g. a polygon with edgesthat form a ”cave” that the watchman route must enter.) The reduction identifiesthese essential regions and uses the fact that the optimal watchman route visits eachregion in a particular order [8].Chin and Ntafos also considered the hardness of the watchman route problemwhere the polygon contains holes in its interior. The authors gave a reductionfrom the geometric (Euclidean) travelling salesman problem to the watchman routeproblem, however errors continued to appear as discussed by Dumitrescu and To´th[9]. Along with an asymptotic upper bound on the length of the shortest watchmanroute with holes defined in terms of the perimeter and diameter of the polygon,Dumitrescu and To´th provided a correct hardness reduction from the rectilineartraveling salesman problem, where the question is what is the shortest cycle thatvisits a set of n points on a lattice structure. Their reduction describes how toshrink the dimensions of each cell of the lattice to form square holes within thepolygon and how to construct an outer boundary. These dimensions allow for theconstruction of cave gadgets, small holes within the polygon that any watchmanroute must enter to see the edges within.5The question of determining the shortest external watchman route was not leftunnoticed, yet interestingly has not been explored as in-depth as its internal coun-terpart. It is clear that the external watchman route problem is at least as hard as theinternal watchman route problem, when the starting point is located on the bound-ary of the polygon, by the following reduction presented by Ntafos and Gewali[18]. The interior of the polygon is converted to the exterior of a new polygon byconstructing a sufficiently large box around the original polygon, but with a thincorridor from the starting position to the external boundary of the box. The resultof this is that the interior of the original polygon now forms a “cave” that must befully explored by an external watchman route. Thus contained within the short-est external watchman route is a subpath that corresponds to the shortest internalwatchman route for the original polygon. Unsurprisingly, the problem of findingthe shortest external watchman route that sees a set of polygons in the plane is NP-hard which can be seen from Dumitrescu and To´th’s reduction by removing theouter boundary of the polygon.Indeed there are many similarities between the two problems due to locality.That is, on a local scale the watchman is not concerned that edges belong to theinterior or exterior of the polygon, only that it is a sequence of edges. Thus onewould imagine that a way to find a shortest path to see a sequence of internal edgescould be used to determine the shortest path that sees a sequence of external edges.This is exactly how the authors in [18] tackle the external watchman route problem.They show that the external watchman route problem can be reduced to a constantnumber of internal watchman route problems on similar polygons (i.e. polygonsthat shared a large number of edges with the original polygon.) The shortest ex-ternal watchman route is then constructed by stitching together the solutions tointernal watchman route problems.In the problems discussed thus far it is assumed that the watchman knows of thepolygon’s structure in its entirety and can therefore plan its trajectory of traversalbefore moving. However an interesting question is what kind of traversal shouldthe watchman take when such information is not initially given, but only revealedby traversing through the plane? Such a problem is interesting as a watchman canonly determine the shortest route by knowing the polygon’s structure. However6without this knowledge a watchman only learns where edges are by inspectingthem. Therefore the information cannot be used to map out the shortest route thatsees a collection of edges.Such problems are considered online in the sense that their input is only par-tially specified to any online algorithm that attempts to solve it. Due to the dis-crepancy between an online algorithm and its optimal offline counterpart, we donot expect an online algorithm to determine the optimal solution. However whenthe solution to a problem can be quantified in terms of a cost function, such as thelength of watchman route produced, we would like our online algorithm to pro-duce a solution that is close to the optimal solution for all instances of the problem.More formally, if for all instances of a problem the cost of the solution produced byan online algorithm on the instance has cost at most c times the cost of the optimalsolution, then we say that the online algorithm is c-competitive, where c ≥ 1 is aconstant called the competitive factor and is independent of the instance size.Problems related to the exploration of a region (e.g. watchman routes) andproblems related to searching for a target in the online setting have been studiedby several researchers. We refer the reader of this thesis to the survey by Goshand Klein [12] which considers several such problems. Relevant to this work isthe one-dimensional search problem known as the cow-path problem where a cow,walking along a one-dimensional fence, is searching for a gate whose positionis unknown. The question is, what strategy can the cow employ (i.e. an onlinealgorithm) such that for all possible placements of the gate the distance the cowtraverses is at most a constant times the distance from the cows initial position tothe gate? Such a problem was first considered by Gal [11] in the context of gametheory, but would later be considered by Baeza-Yates et al. [2] for online searching.In chapter 4 we review a classic doubling strategy for the cow to employ that is 9-competitive and only requires knowledge of a lower bound on the length of thetrue distance the fence is away. As we will see, such a doubling technique is keyto achieving a competitive strategy for the online version of the convex polygoninspection problem.Paramount to a competitive strategy for our problem is how to competitivelylook around several corners. That is, a vertex of the polygon such that one edgeincident to the vertex is seen while the other is not can be considered a corner. If7the agent is at the open end of the seen edge then the shortest path that sees aroundthe corner (i.e. sees the hidden edge) depends on the interior angle formed by thetwo edges. If this angle is less than pi/2 then the shortest path simply hugs the seenedge and moves towards the corner. However if the angle is larger than pi/2 thenthe shortest path moves towards the extension of the unseen edge at a perpendicularangle.As one can imagine a competitive strategy must rotate around the corner to becompetitive for all possible corners. It was Icking, Klein, and Ma that first consid-ered such strategies for a single corner. In [16] the authors present strategies basedon following circular arcs and show that they are indeed competitive. Interestinglya strategy that achieves the smallest competitive factor can be determined by solv-ing a differential equation in polar coordinates. Although an exact solution seemsdifficult to obtain, the authors approximate the optimal competitive factor to beabout 1.212. Dorrigiv, Lo´pez-Ortiz, and Tawfik expanded on the one-corner caseby considering the optimal average-case strategy where the angle of the corner isdrawn from a homogeneous probability distribution [7].Finally we mention the recent work of Tikinsky et al. [22] on the online ver-sion of the convex polygon inspection problem, in which the authors give a 89.83-competitive strategy. In this work the authors define the notion of scope which isa characterization of the unexplored region of the plane in which unseen edges ofthe polygon lie. Namely, from the agent’s starting position there is an unboundedregion of space behind the edges initially seen in which the remainder of the poly-gon is. The boundary of this region are the rays of sight from the initial positionto the furthest counterclockwise and clockwise seen vertices of the polygon; seeFigure 2.2. As the agent explores around the edges of the polygon the rays movein towards one another shrinking the unbounded region, until the region becomesbounded. The angle formed by these rays, once bounded, is the current scope.Once the scope has become bounded, the goal of the agent is to increase the scopeto an angle of pi to ensure all edges are seen.The authors present a strategy that works in two parts: first the agent movesto bound the unseen region, then moves perpendicularly towards the line formedbetween the furthest seen vertices, and repeating until all edges are seen. Theagent employs a doubling search strategy along a line perpendicular to the bisector8(a) Initially the scope (shaded) is unbounded.γ(b) After traversing some distance the scope γ is now bounded as the unseen edges arecontained within a bounded region of the plane.Figure 2.2: The notation of scope from [22]. The agent traverses to firstbound the unexplored region, then collapses it to an empty set; this cor-responds to all edges being seen.9between the two rays of sight that define the unseen region. Once the unseenregion becomes bounded and the scope exceeds pi/8, the second part of the strategybegins. The agent draws a line between the furthest seen vertices and projects itscurrent position onto this line. It then follows the straight line trajectory to thispoint. Upon arrival at this point at least one new edge (possibly more) will beseen. The agent repeats this procedure of drawing a line between the furthest seenvertices in both direction, projecting its current position onto it, and traversingtowards this point until all edges are seen.Through detailed analysis, the authors are able to determine a lower bound onthe length of the optimal path with respect to the lengths traversed by each part oftheir strategy. Interestingly, the strategy only allows the agent to move in straightline trajectories; it does not allow the agent to move along circular curves (or evenmovements that approximate curves.) As we will see in Section 4 by allowing theagent to employ a strategy that uses circular arcs, not only is a smaller competitivefactor achieved but the analysis of such a strategy is much simpler.10Chapter 3The Convex Polygon InspectionProblemIn this section we consider how to determine the shortest inspection path that anagent can take from its starting position to inspect all edges of a convex polygonwhen the polygon is known in advance. We begin in Section 3.1 by defining sev-eral concepts that are key to solving the convex polygon inspection problem. Wethen proceed to define a necessary condition of the shortest inspection path in Sec-tion 3.2; such a condition allows an algorithm to only consider a O(n) number ofpotential shortest inspection paths, where n is the number of edges of the poly-gon. Proceeding with this condition we present a O(n) time algorithm in Section3.3 that determines the shortest inspection path. This algorithm is asymptoticallyfaster than the Θ(n2) time algorithm presented by Tiktinsky et al. in their work’sappendix [22]. We then consider two extensions to the problem. The first specifiesan additional input t, a point external to the polygon, that the agent must reach afterseeing all edges to complete its inspection task. With this additional constraint ofa termination point the shortest inspection path that first sees all edges of the poly-gon, then moves to t via a shortest path may no longer be the shortest inspectionpath. The second extension considers a constraint on the angle α < pi/2 in whichthe agent can see points on an edge. Here the agent can continue to see infinitelyfar in all directions, yet may only inspect a point q from a position p if the raypq makes an angle less that α with the outward normal to the edge q lies on at q.11This implies that the agent cannot see all points of an edge by simply reaching itsextension. Instead, for all points x on the boundary of the polygon the inspectionpath must enter the conic region specified by α and apex x from which x maybe inspected. We derive a similar condition on the optimal solutions for each ofthese problems respectively, and discuss extensions to the algorithm presented todetermine the shortest inspection path.3.1 The ProblemLet Q be a convex polygon in the plane consisting of n edges. Without loss ofgenerality, we may assume that no two consecutive edges of Q (i.e. edges thatshare a common vertex) are collinear. Let e1, e2, . . . , en be the edges ordered in acounterclockwise walk around the polygon. For each edge ei denote its length by|ei|. We define the extension of edge ei as the infinite half-line (i.e. stretching theendpoints of ei to infinity while not translating or rotating the edge) on which eilies and denote it by hi. For two consecutive edges ei, ei+1, we denote the angleformed from edge ei to the extension hi+1 as φi, where the edges en, en+1 ande0, e1 are understood to denote the edge en, e1. The point shared between twoconsecutive edges is a vertex of the polygon defined by an x, y coordinate relativeto the origin of the plane.Consider a mobile agent in the plane modelled as an infinitesimally small pointinitially positioned exterior to Q (possibly on its boundary ∂Q.) At any point pexterior to the polygon the agent can see a point q if the line segment pq does notintersect any obstacle. In this work the only obstacle is the polygon itself. Theagent has fully seen an edge if the agent has traversed a path such that all points ofthe edge are visible from some part of the path. The goal of the agent is to fullysee all edges of Q while traversing a path of minimum length. Once all edges arefully seen the agent’s task is complete.3.2 Properties of a Shortest Inspection PathThere are several properties that must hold for any inspection path to be a shortest(optimal) inspection path. By considering these properties we can devise an effi-cient algorithm to solve the convex polygon inspection problem when the location12(a) A crossing contact. (b) A reflecting contact. (c) A tangential contact.Figure 3.1: A path may contact an edge extension in one of three ways. Notefor a tangential contact the path may or may not enter the half-space(whose boundary is the edge extension) after traversing along the edgeextension.of all edges are known to the agent in advance.A path is feasible if it is contained outside of the polygon, possibly on itsboundary. An inspection path P for a polygon is a feasible path from which everypolygon edge can be seen. Observe that an agent sees an edge ei once it enters thehalf-planeHi with boundary hi collinear with ei that does not contain the polygon.In this work we assume that it is sufficient for the agent to only reach hi to seethe edge as an infinitely small distance can be traversed to enter the region Hi inwhich straight lines from the agent’s position to all points on ei do not intersectthe polygon. There are several ways in which edges can be seen by traversingP . Some edges are initially visible from s, while the remainder are seen when Pcontacts their respective extensions. We borrow the following terms from the studyof the watchman route problem due to the similarity of seeing edges between thetwo problems [3, 5].A contact of P is a non-empty, connected intersection of P with the extensionof a polygon edge. A contact is crossing if it is a point and the points on the pathimmediately before and after the contact lie on different sides of the extension; seeFigure 3.1a. Otherwise, a point contact is reflecting unless it is an endpoint of P ;see Figure 3.1b. A contact that is not at a single point is tangential; see Figure 3.1c.We now begin our discussion on what properties a shortest inspection path Pmust have. For P to be an inspection, P must either contact hi or enterHi for eachedge ei. We partition P into subpaths at the points where P first sees each edge ofthe polygon. Let v1, v2, . . . , vk for k ≤ n be these points, in order, along P withv1 = s. If P is a shortest inspection path then vk = t where t is the end of P .13We replace the subpath of P from vi to vi+1 with the shortest feasible path fromvi to vi+1 for 1 ≤ i ≤ k − 1 such that the ordering in which edges are first seenremains the same. Thus the new path is no longer than P and since it goes throughthe points v1, v2, . . . , vk, it remains an inspection path. Therefore we may assumethat a shortest inspection path has this canonical structure: a sequence of shortestfeasible subpaths between first visits to half-planes whose boundary contains anedge of the polygon. As a consequence of this structure, and the fact that a feasiblepath avoids a polygon, the triangle inequality establishes that an inspection pathconsists only of straight line segments. We refer to these properties as follows:Property 1. (Canonical Structure) A shortest inspection path is composed of se-quence of shortest paths to points on the extensions of edges not seen from s.Property 2. A shortest inspection path consists only of straight line segments (i.e.the path does not contain curves.)Naturally the convexity of Q ensures that an agent following a continuous,feasible path will inspect a continuous part of Q’s boundary.Lemma 3.2.1. Any feasible connected path sees a connected subset of the bound-ary of a convex polygon.Proof. Suppose a path P sees a disconnected subset of the boundary of a convexpolygonQ. Let a and b be two points in different components of the boundary seenby P and let x on ei and y on ej be two boundary points not seen by P , where aclockwise (resp. counterclockwise) walk from a to b along the boundary reachesx (resp. y). Let U be the union of Q, Hi, and Hj . Since the visibility region ofany point on a convex polygon extends to infinity, any path (such as P ) connectingthe visibility region of a with the visibility region of b must cross U . Since P isfeasible, it must reach Hi or Hj ; see Figure 3.2. This is a contradiction.The convexity of Q also gives rise to an order in which edges, not seen from s,will first be inspected by traversing along shortest inspection path.Lemma 3.2.2. Let P be a shortest inspection path and let epi(1), epi(2), . . . , epi(n)be the order in which P first sees each edge of the polygon. Then either pi(n − 1)14eisejxyabFigure 3.2: Proof of Lemma 3.2.1. In blue are the two disconnect subchainsof the boundary seen from the the path in red. As the path cannot tra-verse through the polygon, other edges must be seen from the path thatconnects the two chains.is pi(n) + 1 or pi(n)− 1, up to reordering equivalent elements. That is, the secondto last edge of the ordering is a neighbouring edge of the last edge of the ordering.Proof. Suppose pi(n − 1) is pi(n) − 1. Consider the subpath of P from s to justbefore the first contact with hpi(n)−1. This subpath sees all edges of Q exceptepi(n−1) and epi(n) which by Lemma 3.2.1 must be contiguous. The same argumentholds for pi(n− 1) being pi(n)− 1.Theorem 3.2.3. Let P be a shortest inspection path with j ≥ 2 reflecting contacts.Then an inspection path P ∗ can be constructed from P with j−1 reflecting contactswhose length no longer than P .Proof. LetP be a shortest inspection path with j ≥ 2 reflecting contacts v1, v2, . . . , vj .As P is a shortest inspection path these points must be on edge extensions of edges15not seen from P prior to reaching each of these points.We construct a new path P ∗ by replacing the subpath P [s, v2] in P by the short-est path from s to v2 removing at least one reflecting contact. P ∗ then continues tofollow the remainder of the path P from v2 to the point t where P ends.Observe that P ∗ is indeed no longer than P . To see that P ∗ still forms aninspection path we show that any edges seen on the subpath P [s, v2] are still seenfrom P ∗. From P [s, v2] a connected subchain of edges C is seen. Let w be thenext first contact with an seen edge extension of an edge not yet seen on P [s, v2];such a visit exists as there is at least one edge left unseen. As v2 is a reflectingcontact and w is the first contact with an edge extension not yet seen, Lemma 3.2.1implies P ∗[v2, w] sees a connected subchain of edges C ′ that is a superset of C,see Figure 3.3.The procedure of successively removing reflecting contacts can be repeateduntil the remaining inspection path consists of at most one reflecting contact. Thisprovides the basis for the algorithm we present in the following section.Note the proof of Theorem 3.2.3 implies that any shortest inspection path witha reflection crossing only serves to correct the positing of s. Namely as the subpathfrom v2 to t sees all edges the subpath forms an inspection path. Therefore if oneis allowed to choose the location s to start the inspection of the polygon, the place-ment of s that results in the shortest inspection path is at a point on the extensionwhere the reflecting contact lies.Corollary 3.2.3.1. If we may choose the starting point of our inspection path thenthere is a shortest inspection path that contains no reflecting contacts.Proof. Let P be a shortest inspection path containing a single reflecting contact v.The proof of Theorem 3.2.3 implies that the subpath from v to the endpoint of Pis an inspection path. Thus by moving the starting position of P to v the resultinginspection path contains no reflecting contacts and is no longer than P .We now arrive at the key implication of Theorem 3.2.3 for an algorithm todetermine the shortest inspection path from s when the edges of the polygon areknown. We compute all possible inspection paths of shortest length which consists16sv1v2v3we1e2e3e4e5e6e7Figure 3.3: Proof of Theorem 3.2.3. The first reflecting contact at v1 of theblue path P can be removed to construct the red path P ∗ that movesfrom s to the reflecting contact at v2. The edge that is seen at v1 on theblue path is now seen by a crossing contact on the red path. The chainof edges C = {e1, e2, e3, e4} seen from P [s, v2] is a subset of the chainC ′ = {e1, e2, e3, e4, e5} seen from P ∗[v2, w].of at most one reflecting crossing. As there areO(n) such paths, if we can precom-pute the needed distances to determine the lengths of such paths in O(n) time, wecan simply iterate through each path and report that which has minimum length.The following is an interpretation of our algorithm by imagining the startingposition s to be a ring fixed in the plane. Each edge has a ring which can freely slidealong the edge’s extension. The algorithm threads a string, with one end tied to thering at s, through all the rings; this corresponds to seeing all edges. The string isthen pulled taut, allowing the non-fixed rings to slide ensuring the inspection pathis as short as possible, given the order in which the string is threaded through therings.However by our results above we do not need to consider all possible orders inwhich we can thread the string through the rings. For an edge ei not seen from swe17construct a inspection path which makes a reflecting contact with a neighbouringedge, say ei−1. By tying the string at the ring on hi, we move the string onto oneside of the polygon such that the string, once threaded through the ring on hi−1,traverses through all half-spacesHi. Finally we thread the string through the ring ats then pull it taut. We perform this procedure for each ei not seen from s (ensuringthat we consider both ei−1 and ei+1 for the reflecting contact), along with the twoinspection paths that do not contain reflecting contacts, and report the path withminimum overall length.3.3 A Linear Time AlgorithmIn this section we present a O(n) time algorithm to determine the shortest inspec-tion path from a specified starting point s that sees all n edges of a convex polygonQ. Having described the structure of the shortest path from s by way of an analogyto threading a string through several rings and making it taut we now explicitlyrealize these ideas through primitive operations.Suppose ei is the last edge to be seen by the shortest inspection path. By theresults from Section 3.2 we know that a neighbouring edge (say ei+1) is secondlast in the ordering of edges seen for the first time, with ei−1 coming earlier in thisordering. If ei−1 is seen from s then we compute the shortest inspection path froms to a point on the extension of ei. Otherwise we compute a point p ∈ hi−1 suchthat the resulting path makes a single reflecting contact at p, then traverses towardsa point t ∈ hi such that the subpath from p to t sees all edges. The choices of pand t must be made to ensure that the resulting inspection path has minimal lengthyet is feasible.We characterize such paths P as follows where the superscript i on points de-notes that edge ei is the final edge to be seen for the first time from P and is omittedwhen the context is clear. From s the agent traverses towards a point pi ∈ hi−1.The straight line path from s to pi may intersect Q in which case the path needs tocontact and follow part of ∂Q. Let ai and bi denote the points at which the sub-path from s to pi first contacts ∂Q and last contacts the ∂Q respectively. Makinga reflecting contact at pi the path turns and moves to a point ti on hi such thatthe subpath from pi to ti sees all edges of Q. Again this subpath may or may not18contact ∂Q. If so we denote ci and di as the points at which the path first contactsand last contacts the boundary respectively. By the canonical structure of a shortestinspection path the points ai, bi, ci, and di are vertices of Q. The path then followsa straight line from di to ti to complete the inspection.Therefore the overall inspection path is the concatenation of the subpaths:P [s, ai] + P [ai, bi] + P [bi, pi] + P [pi, ci] + P [ci, di] + P [di, ti]Some of these subpaths may be trivial if, for example, there is a feasible straightline path from s to p in which case a = b = p. For each pair of edges ei−1, ei wedetermine the points ai, bi, pi, ci, di, and ti as needed for the shortest inspectionpath that sees ei−1 by making a reflecting contact on hi−1 and that sees (for thefirst time) edge ei last. Note that we also do this for the other neighbouring edgeof ei, say ei+1 where ei+1 is seen by making a reflecting contact on hi+1. Thiscorresponds to two paths; one which initially traverses in one direction around Q,and the other which initially traverses in the opposite direction. For a shortestinspection path that makes a reflecting contact at a point p, there are three possiblecases: the path does not contact the boundary of Q either before or after reachingp, the path makes contact with the boundary of Q before and after reaching p, andthe path makes contact with the boundary of Q only after reaching p. Note thata shortest inspection path that contacts the boundary of Q before reaching p mustagain contact the boundary of Q after reaching p.Preliminaries: To begin, we describe how to quickly determine the length of achain of Q between two vertices. Recall from above that an inspection path mayfollow the boundary between vertices ai and bi in one direction and ci and di in theother. It is therefore convenient to maintain a data structure to quickly look up thelength of any consecutive chain of edges.Let e1, e2, . . . , en be an arbitrary counterclockwise ordering of the polygon’sedges. Let T (i) denote the length of the chain of edges from e1 up to and includingedge ei. We calculate in O(n) time T (0) = 0 and T (i) = |ei| + T (i − 1) for all1 ≤ i ≤ n. The length T (i, j) of the chain from ei to ej in the counterclockwise19direction is:T (i, j) =T (j)− T (i− 1), i ≤ jT (n)− T (i− 1) + T (j), i > jwhich can be calculated in constant time for a given i and j after calculatingT (1), . . . , T (n).Next we determine the points where a shortest inspection path, traversing along∂Q, must leave the boundary to complete its inspection. A shortest inspection pathmay only leave the boundary from the vertex w that supports a tangent line per-pendicular to hi to reach point ti on hi. There are two such vertices, both of whosetangent lines are parallel to one another that sandwich the polygon. Denote such avertex as the jump-off point for edge extension hi. We can determine the jump-offpoints for each edge extension as follows. Let e1, e2, . . . , en be a sequence of edgescorresponding to a counterclockwise walk around Q. In O(n) time we determinethe vertex w corresponding to the jump-off point for e1. Then for each subsequentedge ei in the ordering we apply a modified rotating caliper technique [23] to deter-mine the jump-off point for hi. The modification required is to ensure that the twolengths that correspond to the calipers are kept at a right angle to hi ; see Figure 3.4.We determine the jump-off points for both counterclockwise and clockwise walksaround Q. Let wiccw and wicw denote the vertices at which a shortest inspectionpath jumps-off the boundary to reach hi at a perpendicular angle by traversing inthe counterclockwise and clockwise directions respectively.No contact with ∂Q: Of course it is possible that the shortest inspection pathreaches the edge extensions hi−1 and hi without ever contacting ∂Q (i.e. a shortestinspection path consisting of two line segments.) Let θi denote the interior anglebetween two consecutive edges ei−1 and ei. If θi ≥ pi/2 then such a shortest in-spection path would not contain a reflecting contact at pi since the shortest feasiblepath from pi (on hi−1) to hi would continue around Q in the same direction as the(straight-line) path from s to pi.If θi < pi/2, we compute the shortest path consisting of two line segmentsthat reach both extensions; see Figure 3.5. The placement of pi and ti can be20e1e2e3e4e5e6e7e8e9w5ccw, w6ccww4ccwFigure 3.4: The jump-off vertices and their projections onto respective edgeextensions for an agent traversing in the counterclockwise directionaround the boundary of Q. Labelled are the vertices w4ccw, w5ccw, andw6ccw along with their projections onto h4, h5, and h6 respectively.determined in constant time as the inspection path is simply the two line segmentsspi and piti such that the latter path reaches hi at a perpendicular angle. The sumof these two lengths forms a convex objective function whose derivative, equatedto zero, determines the location of pi; ti is then the perpendicular projection ofthis point onto hi. It is also a classical result of Heron of Alexandria in 100 C.E.which extends Euclid’s work on optics [6, 13]. Given s, ei−1, and ei, we term theabove operation that returns pi on hi−1 the Heron-operation. Having computedthe jump-off points for hi earlier, we simply need to determine if ti, the projectionof the point returned by the Heron-operation onto hi, is not contained betweenthe projections of wicw and wiccw onto hi. If this is the case the path producedis feasible and thus is the shortest inspection path. Otherwise the subpath pititraverses throughQ and is not feasible. Therefore after the shortest inspection path21eiei−1spitiθidwicw wiccwFigure 3.5: A shortest inspection path which does not contact the boundary ofQ. The location of pi (which dictates the location of ti) is the distanced tan(θi) from the projection of s onto hi−1 towards the endpoint ofei−1 resulting from the solution of setting the derivative of the path’slength to zero. The path is feasible as ti is not located between theprojections of wicw and wiccw onto hi.makes a reflecting contact with hi−1 (at a new pi) the path will make contact with∂Q at some vertex ci. It then follows along the boundary in the clockwise directionuntil the jump-off vertex wicw is encountered and where a straight line path to hi isnow feasible (at a new ti.)Contact with ∂Q before and after the reflecting contact: We now determine if theshortest inspection path from s makes contact with ∂Q before reaching hi−1. If sothe inspection path consists of a line segment to a vertex ai of Q seen from s andthen follows ∂Q until bi = wi−1ccw is encountered. It then moves to hi−1 making areflecting contact and returns to wi−1ccw , and follows ∂Q until wicw is reached when astraight line path from wicw to hi is feasible. wi−1ccw and wicw make the points ci anddi respectively. To determine this we project s, wi−1ccw , and wi−1cw onto hi−1. If theprojection of s lies in between wi−1ccw and wi−1cw then the straight line path from s tohi−1 is not feasible; see Figure 3.6. Therefore the shortest inspection path makescontact with ∂Q before reaching hi−1. To determine the vertex where the path firstmakes contact with ∂Q we identify all edges initially seen from s. By convexityof Q, these edges form a chain whose endpoints are the possible such vertices.The22sei−1eiai = uccwbi = wi−1ccw = cidi = ti = wicwpi = projhi−1wi−1ccwprojhi−1sprojhi−1wi−1cwFigure 3.6: As the projection of s onto hi−1 is contained in between the pro-jections of wi−1ccw and wi−1cw onto hi−1 the shortest inspection path con-tacts the boundary of the polygon before reaching hi−1.chain and its endpoints can be determined easily in O(n) time.We denote the vertices that are the endpoints of this chain uccw and ucw, wheretraversal from uccw to ucw by following the edges ofQ not seen from s is a counter-clockwise traversal around Q. Thus the inspection path is constructed as follows:from s it moves to ai = uccw by a straight line segment then follows the bound-ary of the chain from uccw to bi = wi−1ccw in the counterclockwise direction aroundQ. It then makes a reflecting contact at the projection pi of wi−1ccw onto hi−1. Thepath returns to ci = wi−1ccw and follows the boundary of the chain in the clockwisedirection until di = wicw is encountered. Finally the inspection path reaches hi bymoving to the projection ti of wicw onto hi completing the inspection.Contact with ∂Q after the reflecting contact: The final remaining case is whenthe shortest inspection path only contacts ∂Q after reaching hi−1. Here the short-est inspection path makes a reflecting contact with hi−1 at a point p between theprojections of s and wi−1ccw onto hi−1, yet it is not clear at which vertex q the paththen contacts ∂Q as it traverses in the clockwise direction around Q to wicw. Givens, q, and ei−1 the path consisting of two line segments from s to q that contacts23e1e2e3 e4e5e6e7e8e9w5ccww5cwp5p4p3p2projh5w5ccwprojh5w5cwprojh5sFigure 3.7: Determining where the inspection path makes contact with hi−1before contacting ∂Q. Edges e1, e2, e3, and e4 are candidate edges forthe bounce-operation, and subpaths that reach each respective edge ex-tension are shown. In red is the shortest inpsection path that makes areflecting contact on h4, then moves to h5.hi−1 at a point p can be expressed as a convex function of p. Thus by setting itsderivative to zero we can determine the position of p on hi−1 that yields the short-est such path in constant time. We term the above operation that, given s, q, andei−1, yields the point p on hi−1 visited by the shortest path from s to hi−1 to q asthe bounce-operation.To ensure an overall runtime that is linear in the number of edges of Q, we de-termine p and q for all possible edges ei−1 in O(n) time using the rotating caliperstechnique mentioned earlier. For each edge ei, if the projection of s onto hi isnot contained between the points the projections of wiccw and wicw onto hi, then astraight line path from s to hi is feasible. Otherwise the shortest inspection pathwill contact ∂Q before making a reflecting contact; see Figure 3.7.To simplify the notation for what follows, we label the edges ofQ as e1, e2, . . . , enin counterclockwise order starting with the clockwise-most edge not seen from s;24sei−1eipq∗ pqq∗qFigure 3.8: By triangle inequality, the path spq∗ + pq∗q∗ will be shorter thanspq + pqq + qq∗see Figure 3.7. Let ek+1 be the first edge in this sequence where the projection ofs lies within the projection of Q on hk+1. So ek+1 is the first edge where a shortestinspection path must contact ∂Q before reaching hk+1.We first determine the shortest inspection path that makes a reflecting contacton edge extension hk using the bounce-operation. Given s and hk, we start atjump-on vertex q = wkccw and advance q clockwise until we find vertex q∗ that isthe last feasible vertex (i.e. the shortest path from s to hk to q∗ avoids the interiorof Q.) By convexity of the polygon, we can ensure that inspection paths generatedfrom s to hk to q for all q before q∗ will be longer than the inspection path from sto hk to q∗. This follows by successive applications of the triangle inequality andthe fact that all paths that contact ∂Q at q must traverse along the boundary in theclockwise direction, eventually reaching q∗; see Figure 3.8.The point returned from the bounce-operation for s, ek, and q∗ is the pointpk+1, with ck+1 = q∗. The inspection path then continues along ∂Q until dk+1 =wk+1cw is encountered, and then proceeds to t = projhk+1wk+1cw .We now determine the shortest inspection path from s that makes a reflectingcontact on ek−1. We claim the first vertex that needs to be considered as a jump-onvertex for the path is the vertex q∗. That is, as the vertices q already consideredare not the jump-on vertex for the shortest inspection path that makes a reflecting25contact on hk, they cannot be the jump-on point for the shortest inspection paththat makes a reflecting contact on hk−1. By convexity of the polygon, spk+1 mustcross hk−1; denote this point as p′. The path sp′ + p′q∗ makes a reflecting contactwith hk−1, is shorter than spk+1+pk+1q∗ by the triangle inequality, and is feasible.Now suppose the shortest inspection path that makes a reflecting contact with hk−1reaches a jump-on vertex already considered. As the resulting inspection path musttraverse along the boundary and reach q∗, such an inspection path cannot be shorterthan sp′ + p′q∗.We continue a clockwise walk around Q to determine the vertex q∗ that theshortest inspection path from s to hk−1 to Q uses to contact the boundary. Wethen repeat this procedure to determine the shortest inspection paths that see edgese1, e2, . . . , ek by a reflecting contact.Let mj denote the number of times the bounce-operation is performed to com-pute the shortest inspection path which makes a reflecting contact on hj for j =1, 2, . . . , k. Since every bounce operation results in a clockwise advance of q∗ or adecrease in the index j, the total number of bounce operations is at most n+k ≤ 2nand so the overall runtime to determine all such shortest inspection paths is O(n).The above procedures determine the shortest inspection path which leaves sby traversing in the counterclockwise direction around the polygon and makesa reflecting contact on the extension of an edge not seen from s. By mirroringthese operations, we can determine the shortest inspection paths which leaves s bytraversing in the clockwise direction and make a reflecting contact. Over these twopaths, we maintain the path of overall shortest length.No reflecting contact: The final case to consider is when the shortest inspectionpath makes no reflecting contact. From the chain of edges seen from s let ei+1and ej−1 be the final edges of the chain and ei and ej the neighbouring edges notseen from s respectively. The two shortest inspection paths left to consider are theshortest paths from s to hi and hj such that all edges ofQwill be seen from the pathand neither paths contain reflecting contacts. Such paths either contact or do notcontact ∂Q. Using the procedures described earlier in this section, we can easilydetermine if contact with ∂Q must be made. If so, the path starts with a straightline from s to the seen-from-s endpoint of ei (ej) then follows the boundary of the26polygon until a straight line path to hj (hi) is feasible. Overall we will comparethese path lengths to the shortest inspection path that contains a reflecting contactand report the shortest overall path.We conclude by considering the case where the agent can choose its start-ing position s to minimize the length of the resulting inspection path. By Corol-lary 3.2.3.1 and the canonical structure of the shortest inspection path, we chooseto place s on some edge extension hi−1 such that the path ending on hi sees alledges of Q. Such a position is the projection of wi−1ccw onto hi−1. We can thendetermine the inspection paths resulting from all candidate starting locations andreport the inspection path of shortest length.3.4 Extension: A Specified Termination PointWe now consider an extension to the polygon inspection problem where the inspec-tion path must terminate at a specified point t exterior to the polygon. We build onthe results from the earlier sections to determine the shortest inspection path withboth specified starting and ending points. Extending Theorem 3.2.3, which impliedthat the shortest inspection path will consist of at most one reflecting contact, wewill see that in this scenario the shortest inspection path may consist of at most tworeflecting contacts and if there is a second reflecting contact on extension hi, thenedge ei is the last edge inspected for the first time from the inspection path P . Thisoccurs only when it is shorter to reach t by making a reflecting contact on hi ratherthan making a tangential or crossing contact.Theorem 3.4.1. Let P be a shortest inspection path starting at s and ending att. Then P consists of at most two reflecting contacts. Further if P does contain asecond reflecting contact at a point p2, then p2 is located on the extension of thefinal edge to be seen for the first time from P .Proof. The proof that P consists of at most two reflecting contacts is similar tothe proof of Theorem 3.2.3; any shortest inspection path that contains at least threereflecting contacts can be shortened to an inspection path containing one less re-flecting contact that still inspects all edges of the polygon and ends at t.Suppose p1 is the first of exactly two reflecting contacts of P . By contradic-27tion assume that reaching the second reflecting contact p2 does not complete theinspection of the polygon. Thus the subpath P [p2, t] contacts the extension of thelast edge to be inspected for the first time from P ; let this point be p′. As P con-tains exactly two reflecting contacts p′ is either a tangential or crossing contact.We construct a shorter inspection path by replacing the subpath P [s, p2] with theshortest path from s to p2, then continuing along P [p2, t] through p′; see Figure 3.9.Denote this path as P ∗. Observe that P ∗ is no longer than P and consists of only asingle reflecting contact.To see that P ∗ forms an inspection path, observe that p2, say on hi−1, is thefinal reflecting contact of P . As the inspection is not finished when p2 is reached, itmust be the case that p′ lies on the extension of the neighbouring edge of ei−1. Byconvexity of the polygon, the subpath P ∗[p2, t′] inspects all edges of the polygon.Therefore P is not a shortest inspection path.Theorem 3.4.1 allows for an efficient algorithm to determine the shortest in-spection path with specified starting and ending points. As described in Section 3.3we compute all shortest inspection paths consisting of either one or zero reflectingcontacts which inspect edge ei last. As t is specified we can no longer use therotating calipers technique to determine the vertices of the polygon where the in-spection path leaves (if it at all touches) the boundary to reach a point on hi. Rather,the vertex di is the first vertex on the boundary of the polygon such that a straightline path from di to t is feasible and will contact hi before reaching t. In the sameway we determined the endpoints of the chain seen from s we can determine theendpoints of the chain seen from t; these vertices correspond to the positions whereinspection paths will leave the boundary to move towards t.Finally we compute all shortest inspection paths which consist of two reflect-ing contacts. As the second reflecting contact must complete the inspection of thepolygon, we consider all pairs of consecutive edges ei−1, ei such that the first re-flecting contact is made at pi1 on hi−1, the second at pi2 on hi and that the subpathfrom p1 to p2 sees all edges. We apply the techniques described in Section 3.3 todetermine at which vertex (if at all) the shortest inspection path contacts the bound-ary before reaching p1 and then where it contacts the boundary before p2. These28stp1p2p′Figure 3.9: Proof of Theorem 3.4.1. A shortest inspection path that does notcomplete inspection upon making a second reflecting contact can beshortened to an inspection path with only one reflecting contact.techniques are also used to determine at which vertex the inspection path leaves theboundary before reaching p2 and where it contacts the boundary again as it movestowards to t.Once the lengths of all shortest inspection paths are computed we simply reportthe path of minimum length.3.5 Extension: Constraints on Inspection AngleIn this section we consider the addition of a constraint on the angle in which anedge can be inspected, given the agent’s position. Now the agent is no longersatisfied with looking down the length of an edge to inspect its points. Instead, anangle 0 ≤ α ≤ pi/2 is specified as part of the input where a point x on edge eiis visible by the agent if and only if the agent is within (or on the boundary of)the infinite conic region exterior to the polygon with apex x, whose angle is 2α,29and whose major axis is perpendicular to hi; see Figure 3.10a. Term this region ofspace as the inspection region of x and denote it as IRi(x). Further let IRiL(x) andIRiR(x) denote the two boundaries of IRi(x). When x is a vertex of the polygonit is ambiguous what the inspection region should be given that there are two conicregions, one for each edge incident to x. We define the inspection region of a vertexto be the union of cones whose major axis is perpendicular to some tangent of Q atx; see Figure 3.10b. When α = pi/2 we have the original version of the polygoninspection problem.As it is no longer sufficient for an inspection path to simply reach the extensionof an edge to inspect it, it is not clear that the results of Sections 3.2 and 3.3 can bemodified to handle this version of the problem. To explore the differences betweenthe two problems we first make the following observations.First for any starting point s exterior to the polygon some portion of the poly-gon’s boundary is seen since every point exterior to the polygon is in some inspec-tion region.Second, from a single point, the agent may only see part of an edge. Forexample, if s is on the boundary of the polygon and α < pi/2, the only part ofthe boundary seen from s is s itself.And third, the shortest inspection path consists of at most one reflecting contactwith the boundary of some inspection region. This follows in a similar fashion asthe proof of Theorem 3.2.3; any shortest inspection path with at least two reflectingcontacts with some inspection regions can be shortened to a path with one fewerreflecting contacts that still sees all edges of the polygon.Similar to when α = pi/2, when we inferred that a shortest inspection paththat makes a reflecting contact on hi terminates on the extension of a neighbouringedge of ei, we can infer:Lemma 3.5.1. Let P be a shortest inspection path with inspection angle α whichends at a point t. Then there exists a point x on the boundary of the polygonsuch that t lies on the boundary of IR(x) and P makes contact with the oppositeboundary of IR(x) before t.Proof. As P is a shortest inspection path, P terminates once all edges of the poly-gon are seen. If t was not located on the boundary of an inspection region then t30αx2α(a) A point x of the polygon is only visible if the agent is positioned within or on the bound-ary of the infinite conic region with angle 2α. The conic region’s major axis lies perpendicularto the edge the point is on.(b) The inspection region of a vertex is the resulting union of cones whose major axes areperpendicular to tangents of Q at the vertex.31must be located in the interior of an inspection region of a vertex of the polygon.However P could then be shorted to the point where it first enters the inspectionregion to see the vertex.Suppose t is on the boundary, called IRL(x), of the inspection region IR(x)with IRR(x) denoting the opposite boundary.Consider a tiny interval along the boundary of the polygon centered at x. Justbefore reaching t, P sees all points of the boundary within this interval on one sideof x. As P must see all edges fully and P terminates at t, it must be the case thatthe points contained within the interval on the opposite side of x are seen from Pas well.As a shortest inspection path contains at most one reflecting contact, an inspec-tion path that makes a reflecting contact on one boundary of IR(x) must terminateon the opposite boundary of IR(x). If the path contains no reflecting contact thenthe path terminates on a boundary of the inspection region of a point seen from s.We now show that a shortest inspection path is constrained to making a reflectingcontact only on the boundary of a vertex’s inspection region.Theorem 3.5.2. A shortest inspection path with inspection angle α that makes areflecting contact must do so on the boundary of IR(v) for some vertex v of thepolygon.Proof. Let t be the endpoint of an inspection path P such that t lies on IRiL(x)for an interior point x on edge ei. We first suppose no portion of ei is seen froms. Let v be the shared endpoint of ei and ei−1 such that v is seen from P beforemaking a reflecting contact at p on IRiR(x). We construct a shorter inspectionpath P ∗ from P that contains one reflecting contact by constructing a sequenceof shortest inspection paths, such that each subsequent path is no longer than theprevious. This sequence of paths results from first translating the point at x alongei towards v, then rotating the inspection region of this point until its major axis isperpendicular to edge ei−1.For  > 0, let x+  be the point on ei that is distance  from x between x andv. The new inspection path makes a reflecting contact on IRiR(x + ) at point p,then moves to t such that all edges except ei are guaranteed to be fully inspected.32To complete the inspection of ei, P ∗ must reach a point t on IRL(x + ) via ashortest path. That is, the new inspection path consists of the shortest path from sto p, then to t and finally to t such that all edges except ei are fully seen from pto t.The shortest distance between t and t is  sin(α). However the previous in-spection pathP traversed at least twice this distance on its way to and after reachingp; see Figure 3.11. Thus the shortest inspection path that makes a reflecting con-tact on IRiR(v) is no longer than the shortest inspection path that makes a reflectingcontact on IRiR(x).Observe that the shortest inspection path which makes a reflecting contact onIRiR(v) makes two crossing contacts with IRi−1R (v). By convexity of the polygonthe portion of the subpath between the crossing contacts does not serve to inspectany new portion of the polygon. Therefore we can eliminate it by constructing ashortest inspection path from s to a point on IRi−1R (v) then to t such that all edgesof the polygon are fully seen.Now suppose some portion of ei is seen from s. We construct a shorter inspec-tion path P ∗ which contains no reflecting contact. Let x be a point on the interiorof ei such that P makes a reflecting contact at point p on IRiR(x), let y on ei be theclosest point to x such that y is seen from s, and t the endpoint of P on IRiL(x).For  > 0, let x +  be the point on ei that is distance  from x between x and y.We construct a new inspection path consisting of the shortest path from s to a pointp on IRiR(x + ) then to t. We again append to this path the shortest path from tto t′, of distance  sin(α) where t′ lies on IRiL(x + ) to ensure that the edge ei isfully seen. Observe that P traverses at least twice the distance  sin(α) to traversefrom IRiR(x + ) to p, then back. Thus P∗ is no longer than P and contains noreflecting contacts.Lemma 3.5.1 and Theorem 3.5.2 allow us to efficiently determine the shortestinspection path with inspection angle α that starts at s. We compute all shortestinspection paths which have at most one reflecting contact and report the path ofminimum length by using techniques similar to those presented earlier.When α = 0 the proof of the Theorem implies that a shortest inspection pathcannot contain any reflecting contact. Namely if a shortest inspection path makes33eiei−1x vsαttbc aIRi−1R (v)IRiR(v)IRiR(x)IRiL(x) IRiL(v)pFigure 3.11: The case when edge ei on which x lies is not seen from s. Inblue is the shortest inspection path that sees x by making a reflectingcontact at p on IRiR(x) and ends at t. This path crosses IRi−1R (v)twice at points b and c. In red is a shorter inspection path which makesa reflecting contact with IRi−1R (v) at point a and ends at t.a reflecting contact with ray IRR(y′) for any y′ 6= y such that s is on IRR(y), bysliding y′ to y and extending the inspection path to t′ on IRL(y) we transform Pinto a shorter inspection path with no reflecting contact.Corollary 3.5.2.1. A shortest inspection path P with inspection angle α = 0 con-tains no reflecting contacts.As discussed in Section 3.2 when α = pi/2 it may be the case that the shortestinspection path contains a reflecting contact. For a given polygon and startingposition s, it would be interesting to understand how increasing α from 0 to pi/2would change the structure of the shortest inspection path. Is there a particularvalue α′ at which the shortest inspection path changes from containing no reflectingcontacts to containing one? If so, does there exist two unique shortest inspectionpaths with equal length, one with and one without a reflecting contact for thisparticular value of α? And finally is there an underlying relationship between sand the vertices of the polygon such that one can determine whether or not theshortest inspection path with inspection angle α contains a reflecting contact? We34leave these open problems with the reader of this thesis to pursue at their ownleisure.35Chapter 4The Online ProblemIn this section we consider the polygon inspection problem where the agent doesnot know the location of edges in advance, only that they form a convex polygon.From an initial position s the agent can see a portion of the polygon but must thentraverse through the plane to see the remainder of the polygon. Only by seeing anedge does the agent learn of its location. This leads to the interesting question ofhow should the agent explore through the plane to inspect the polygon?It is clear that without prior knowledge of the polygon the agent cannot deter-mine the shortest possible inspection path. Yet one would not be content with anagent that requires arbitrarily long paths to see the polygon. As a middle ground,one could ask the agent to generate an inspection path that is approximately thelength of the optimal path. That is, can the agent guarantee that length of theinspection path it produces is at most a constant times the length of the optimalinspection path? Further will this guarantee hold for all possible polygons andstarting positions?If the agent is clever and willing, one could imagine strategies that may workfor certain polygons such as rectangular or triangle shaped polygons, yet it is notapparent if a single strategy would handle all possible convex polygons. Indeed,as seen in Section 3.2 the optimal path may turn once a certain edge is seen (i.e. areflecting contact on some edge extension); a realization that is only possible whenthe location of all edges are known. The concern for an agent in this online scenariois it does not know that it should turn once this edge is seen, and by continuing to36traverse in the same direction, an unacceptably long inspection path may result.Formally, an online algorithm (strategy) A is a method by which the agentwill inspect the polygon from some starting position. We define the cost of such astrategy to be the total distance the agent will traverse to complete the inspection.We denote this cost as |A|. Let O denote the algorithm from Section 3.3 whichdetermines the shortest inspection path. We say that strategy A is c-competitive iffor all instances of the polygon inspection problem, |A| ≤ c · |O| where c ≥ 1 isa constant independent of the shape of the polygon. Such an inequality must holdfor all convex polygons and starting positions.As described above a problem for the agent in the online setting is that it doesnot know when to turn, knowledge that is available to the optimal strategy. To beginour search for a competitive strategy for the convex polygon inspection problem wefirst investigate a simpler subproblem where the agent (in both offline and onlinescenarios) can only traverse in one direction around the polygon to see a chainof its edges. In Section 4.1 we define this subproblem and give a 2pi-competitivestrategy for it.In Section 4.2 we then show how any strategy that is c-competitive for thesubproblem can be incorporated in a strategy that is 9c-competitive for the con-vex polygon inspection problem by incorporating techniques used for searching intwo directions. A consequence of this yields an 18pi-competitive strategy for theconvex polygon inspection problem when the the subproblem strategy presented inSection 4.1 is used.Then in Section 4.3 we build on the work of Hoffman et al. to show thattheir angle hull operator, a way to generate a closed path around a convex polygonwhose length is at most pi/2 times the length of the polygon’s boundary, can beextended to a strategy for the subproblem whose resulting path is no longer thanpi/2 times the shortest inspection path that sees the chain of edges. By then usingthis improved strategy in the strategy for the convex polygon inspection problemwe arrive at a 4.5pi ≈ 14.14-competitive strategy.374.1 The Convex Chain Inspection ProblemA chain of length k is a sequence of edges e1, e2, . . . , ek such that only edges(ei, ei+1) share a common vertex for i = 1 to k − 1 with edges e1 and ek eachhaving one unshared (open) endpoint. By convex chain we mean a chain of edgesthat originates from the boundary of a convex polygon. A convex chain may bedirected clockwise or counterclockwise following the corresponding orientation ofthe polygon boundary. The edge e1 is the first edge in such a directed chain. TheConvex Chain Inspection problem is given a starting point s from which edge e1of a directed chain is visible (and possibly other edges), what is the shortest pathfrom s that will see all edges of the convex chain such that the agent traverses inthe direction of the chain?The shortest path for the convex chain problem will result in the agent onlytraversing in one direction (e.g. counterclockwise) around the chain. As the chainis convex such a path from the starting position to a point on the extension of thefinal edge is guaranteed to see all edges of the chain. Thus the optimal path issimply the shortest path from the starting position to a point on the extension of thelast edge.However we are concerned with what an agent should do if this chain is notknown in advance. We assume that the agent is aware that the chain is convexand its size (i.e. it can detect when all edges have been seen.) From the agent’sstarting position there will be a corner which the agent must look around. Lookingaround this corner will reveal the next unseen edge of the chain and, if more unseenedges remain, the next corner to look around. Thus a strategy for the convex chainproblem generates a trajectory for the agent to follow as it looks around the cornersof the chain. As we are interested in competitive strategies, we wish to determinestrategies in which the distance traversed is at most a constant times the length ofthe optimal inspection path.It was Icking et al. [16] who first considered competitive strategies for an agentto look around a single corner (i.e. a convex chain with 2 edges.) One strategy thatthe agent may employ is to simply traverse to the corner. This may indeed be theoptimal way to look around the corner, but for some corners the competitive factorof such a strategy can be arbitrary large. For instance, consider the agent starting38sφ φsFigure 4.1: Two instances of looking around a single corner where the opti-mal path (in red) either moves away from the boundary or follows theboundary. In blue is the path which follows a circular arc centered at thecorner with radius the distance s is away from the corner.at the open end of the first edge with length u, and let φ be the angle between thefirst edge and the extension of the second edge. The length of the optimal path tolook around the corner is given by|O| =u if φ ≥ pi/2u sin(φ) otherwisewhich for φ ≈ 0 results in a competitive factor that is arbitrarily large.The above suggests that if a strategy is to be competitive, it must move awayfrom the chain, and rotate around the corner. A natural idea for a better strategyis as follows: the agent initially guess that φ is small and estimates where the nextedge’s extension will be. The agent then takes a small step perpendicular to thisestimate. If the edge is still not seen, the agent then updates its estimate for φ (andupdates its estimate for the location the next edge’s extension) and takes anothersmall step. This process is repeated until the next edge is seen.By taking smaller and smaller steps, this strategy approaches a circular arcwhose center is located on the corner with radius the initial distance the agent isaway from the corner; see Figure 4.1. Such a strategy is indeed pi-competitive fora single corner. Continuing with the above example, the competitive factor usingthis strategy is|A||O| =φuu ≤ pi if φ ≥ pi/2φuu sin(φ) ≤ pi2 otherwise.39A strategy with a better competitive factor of pi/2 follows from centering thecircle not on the corner but at the midpoint between the agent and the corner (i.e.the diameter of the circle is the distance from the agent to the corner.) Interestinglythe optimal competitive strategy for the one corner case is a strategy that spiralsin towards to the corner. Such a strategy is the result of a differential equation inpolar coordinates, and although a closed form solution seems difficult to obtain, itsestimation results in an optimal competitive factor of approximately 1.212 [16].While such strategies may be competitive for the single corner case it is notclear if their competitive factors hold for several corners. Let the corner-radiusstrategy be defined as follows: Suppose the direction of traversal is counterclock-wise. From its starting position, the agent follows circular arcs in the counterclock-wise direction where the center of the circle which generates said arcs is the furthestseen vertex in the counterclockwise direction. Once a corner is looked around, anew circle’s center is placed on the next corner to look around with radius equal tothe distance the agent is away from said corner. The agent then continues to movein the counterclockwise direction following the new circular arcs. This process isrepeated until the final edge is seen.We now show that the corner-radius strategy is indeed competitive.Theorem 4.1.1. The corner-radius strategy is 2pi-competitive for the convex chainproblem.Proof. We begin by assuming that the starting position s is located at the openendpoint of the chain and later consider when s is at some other feasible positionthat sees e1. Suppose there are n edges of the chain and let φi denote the exteriorangle between edge ei and the extension of edge ei+1 for 1 ≤ 1 ≤ n− 1.By definition of the corner-radius strategy, to look around the ith corner theagent will rotate by angle φi and be at distance |e1| + |e2| + . . . + |ei| away. Wewill denote the total distance traversed by the agent as |ACR| which is|ACR| =n−1∑i=1φi i∑j=1|ej | = n−1∑j=1|ej |n−1∑i=jφiby rearranging terms.40We now consider the length of the optimal inspection path, starting from s,that sees the chain. To prove the theorem, we will considser how the length of eachedge ei contributes to the length of the optimal path.The optimal path is simply the shortest path from s to the extension of edge enwhich traverses in the direction of the chain. As such, we can partition the length ofthe optimal path into two segments: that which follows the boundary of the chainand that which leaves the boundary moving towards the extension of en. Denotethese lengths as |O‖| and |O⊥| respectively. The overall length of the optimal pathis then |O| = |O‖| + |O⊥|. Note that either of these sub lengths may be zero,depending on the chain.Let eu be the last edge in which the optimal path remains on the boundary ofthe chain (u = 0 denotes that the path leaves the chain’s boundary immediatelyfrom s and u = n − 1 denotes that the path never leaves the boundary.) Thus wehave|O‖| =u∑j=1|ej |Observe that the subpath O⊥ is a straightline segment that ends on the exten-sions of en. We further partition O⊥ into a sequence of base lengths of right trian-gles whose hypotenuses correspond to thes the edges eu+1 to en−1; see Figure 4.2.Thus the length of this subpath is given by|O⊥| =n−1∑j=u+1|ej | sinn−1∑i=jφjWe now make the following observations. First as the chain originates froma convex polygon, the sum of all angles φi is at most 2pi. Second as the optimalpath leaves the boundary after traversing along edge eu the sum of the angles ofthe remaining corners is at most pi/2 (i.e. φu+1 + . . .+ φn−1 ≤ pi/2). Finally onecan easily verify that for x ∈ (0, pi/2), x ≤ pi2 sin(x). Therefore we have:41φ1φ2φ3φ4e1e2e3e4e5sFigure 4.2: An instance of the corner-radius problem. In red is the optimalpath from s that sees all edges and blue is the path resulting from thecorner-radius strategy. Note that the optimal path leaves the boundary atthe vertex shared by e2 and e3; this subpath consists of two right trianglebase lengths.|ACR| =n−1∑j=1|ej |n−1∑i=jφi = u∑j=1|ej |n−1∑i=jφi+ n−1∑j=u+1|ej |n−1∑i=jφi≤ 2piu∑j=1|ej |+ pi2n−1∑j=u+1|ej | sinn−1∑i=jφi≤ 2pi u∑j=1|ej |+n−1∑j=u+1|ej | sinn−1∑i=jφis ≤ 2pi|O|.To conclude the proof we now consider when s is not located at the open end-point of the first edge. As both the optimal path and the path generated by thestrategy must start at the same point, we conclude that as long as s can see the firstedge the competitive factor holds. To see this, we can convert any instance of theconvex chain problem where s is not located at the open endpoint of the first edgeto an instance where it is.42sFigure 4.3: The starting position is off of the boundary of chain. The originalchain with initially seen edges are grayed out and the new chain startingat s consists of three edges. The optimal path and path generated by thecorner-radius strategy are the same for both chains.Let ei be the last edge seen by the agent from s and let ui be the endpoint ofedge ei that is the corner the agent must look around. We construct a new chainby removing edges e1, e2, . . . ei from the old chain, and inserting the single edge(s, ui); see Figure 4.3. Observe that both the optimal path and the path generatedfrom the corner-radius strategy for the new chain is the same as for the old chain.Thus the corner-radius strategy is 2pi-competitive for any s.Note that when the chain is nearly a convex polygon and u = n−1, the corner-radius strategy cannot avoid rotating by an angle of ≈ 2pi. In Section 4.3 we buildupon the angle hull operator to give an improved strategy for the convex chainproblem that is pi/2-competitive.4.2 A Two-Sided Search StrategyIn this section we show how any c-competitive strategy for the convex chain prob-lem can be incorporated into a strategy for the convex polygon inspection problemthat is 9c-competitive. An immediate implication of this is an 18pi-competitivestrategy when the sub-strategy incorporated is the corner-radius strategy from theprevious section. Further, if one can identify strategies for the convex chain prob-43lem with smaller competitive factors, these benefits will be carried over to a strat-egy for the convex polygon inspection problem.Recall that the optimal path to see the edges of the polygon is dictated by thepolygon’s structure as well as the agent’s starting position. For certain instances ofthe problem, the shortest inspection path may require the agent to traverse in onlyone direction, yet for other instances the optimal path may have the agent makea reflecting contact after seeing some edge. For any strategy to be competitive itmust defend against these two possibilities. That is, a competitive strategy willneed to search in both directions around the polygon.A natural approach is to incrementally search in both directions. From s, searchin the counterclockwise direction around the polygon for some distance, if thereremains unseen edges of the polygon, return to s, then search in the clockwisedirection for some distance. The agent repeats this process until the entirety ofthe polygon is inspected. However it is not clear how the agent should choosethese distances and whether any sequence of distances will result in a total distancetraversed by the strategy that is competitive compared to the shortest inspectionpath.To this end recall the 2-lane cow-path problem mentioned in Section 2. Acow with poor eye sight is located at the origin of the real-axis (the fence) and issearching for a gate in the fence at some distance d away. Unaware of the distanced or in what direction, the cow wishes to employ a competitive strategy to searchfor the gate.Key to determining a competitive strategy is knowledge of a lower bound λ ond. If λ is known to the cow then a doubling search strategy where the cow firstmoves in one direction distance λ, returning to the origin if the gate is not found,then traversing distance 2λ in the opposite direction, returning to the origin if stillnot found, and traversing in the first direction a distance of 4λ and so on until thegate is found, is 9-competitive.Such a strategy is exactly what is needed by an agent to be competitive for theconvex polygon inspection problem. As such we include a detail analysis of theabove based on the work of Baeza-Yates et al. [2] who termed the doubling searchstrategy the linear spiral search.44Theorem 4.2.1. Let d be the true distance the gate is located away from the originand λ ≤ d be a known lower bound. Then the linear spiral search strategy is9-competitive.Proof. We begin by asking what is a location of the gate where this strategy pre-forms poorly. At some point in the execution of the strategy the cow will movesome distance d′ away from the origin, stop after not finding the gate, then returnto the origin. This strategy preforms poorly if the the location of the gate was justbeyond this point. That is for small  > 0, d = d′ + .Formally let di = 2(2i−1λ) = 2iλ be the distance traversed by the cow for theith iteration where an iteration consists of the cow moving away from, then backtowards, the origin. Suppose at the kth iteration the cow should have moved theextra  distance to find the gate before turning around. Thus d = 2k−1λ+ .Now consider total distance traversed by the cow |A| before finding the gate:|A| =k∑i=1di + dk+1 + d= 2λ(k−1∑i=02i)+ 2k+1λ+ d= 2(2k+1λ)− 2λ+ d= 2(4(d− ))− λ+ d= 9d− (8+ 2λ)by observing that 2k+1λ = 4(d − ). Finally we consider the ratio of |A| to thetrue distance d and find|A|d= 9− 8+ 2λd≤ 9.Given a lower bound λ on the length of the shortest inspection route, a strategyfor the convex polygon inspection problem now seems clear. From the initial po-sition s the agent follows a strategy for the convex chain problem in one direction45(say counterclockwise) a distance of λ, then returns to s if edges of the polygonremain unseen. The agent then employs the same strategy to search in the opposite(clockwise) direction a distance of 2λ, returning to s if edges remain to be seen andrepeats this processes, continuing to double the distances traversed along the arcsof each of the two strategy instances.Formally, we define the two-sided, C strategy, which uses a c-competitive con-vex chain strategy, for the convex polygon inspection problem as follows. Let λ bea lower bound on the length of the shortest inspection path. Then the two-sided,C strategy uses the trajectories generated by C, in both directions around the poly-gon. The agent chooses one trajectory to initially traverse arbitrarily then employsdoubling search along both until all edges of the polygon are seen.We now show that the combination of a strategy for the convex chain problemand a doubling search in such a strategy results in a competitive strategy. Weassume that the agent knows a lower bound on the length of the shortest inspectionpath; in Section 4.4 we show how the agent may determine such a bound from itsinitial position.Theorem 4.2.2. The two-sided, C strategy is 9c-competitive for the convex polygoninspection problem, where c is the constant competitive ratio of the convex chainstrategy C.Proof. The two-sided, C strategy can be viewed as a type of cow-path problemwhere there are two gates, say L and R, which the cow must search for, yet onlyrealizes it has found any gate once both are discovered. The gates L and R corre-spond to points on the extensions of edges where the shortest inspection path wouldmake a reflecting contact on one extension, then terminate on the other extension.Note that the arcs generated by the two-sided, C strategy are the same arcswhich are generated by two instances of the convex chain problem: one in whichthe agent moves in one direction from s to see edges up to the edge whose extensionL lies on, and one in which the agent moves in the other direction from s to seeedges up to the edge whose extension R lies on.Let p be the point, eitherL orR, that is reached last be the two-sided, C strategy,hp the extension on which p lies, and let |ATS | denote the overall distance traversedby the two-sided, C strategy.46Let |P | denote the length of the shortest inspection path P from s to hp that seesall edges on the corresponding convex chain instance. The C strategy will generatetrajectory whose length is at most c|P |. As the two-sided, C strategy uses the arcsof C to search for p, an application of the the cow-path analysis implies |ATS | ≤9c|P |, where the initial step size is the known lower bound on the length of theshortest inspection path that inspects the polygon. As the shortest inspection pathmust see all edges of the polygon, it must reach both L and R, not just whicheverpoint p is; thus the length of the shortest inspection path is bounded below by |P |.Let O be the shortest inspection path. Then we have |ATS | ≤ 9c|O|.When the corner-radius strategy is used as C in the two-side, C strategy, theo-rem 4.2.2 implies the following:Theorem 4.2.3. The two-side, corner-radius strategy is 18pi-competitive for theconvex polygon inspection problem.4.3 The Angle Hull StrategyIn the previous section we incorporated the 2pi-competitive corner-radius strategyas a sub-strategy for the convex chain inspection problem into an 18pi-competitivestrategy for the convex polygon inspection problem. To achieve a better competi-tive strategy for the convex polygon inspection problem we can replace the corner-radius strategy with a strategy for the convex chain problem that has a smallercompetitive factor. In this section we describe a pi/2-competitive strategy for theconvex chain problem which results from better placement of circle centers whosearcs the agent follows.Using the corner-radius strategy, the agent looks around the ith corner by fol-lowing the arc of a circle centered on the corner with radius |e1|+ |e2|+ . . .+ |ei|and rotating by an angle of φi. While it is necessary for any competitive strategy tomove the agent away from the boundary of the chain, we aim to devise a strategywhich can guarantee that the agent is never too far way from the boundary.To this end we make use of the angle hull of a convex polygon defined by Ickinget al. [14]. The angle hull of a convex polygon is the set of points surrounding thepolygon such that for all points p of the angle hull, the angle between the ray47Figure 4.4: The angle hull of a convex polygon shown in red. For all pointsp on the convex hull, the two rays from p to the furthest seen vertices ofthe polygon form a right angle.from p to the furthest seen vertex in the clockwise direction and the ray from pto the furthest seen vertex in the counterclockwise direction form a right angle;see Figure 4.4. Notice that such a constraint on the angle between the two rayswill generate a circular arc who’s center point is located within or on the boundaryof the polygon. Equivalently, the arc generated lies on the boundary of the circlewhose diameter spans the two furthest seen vertices of the polygon. In [14] theauthors show that the length of the angle hull of any polygon is at most pi/2 thelength of the polygon’s boundary. We show that a strategy based on the angle hullwill generate an inspection path for the convex chain problem whose length is atmost pi/2 the length of the optimal inspection path for the chain.Before we formally define the strategy we must consider an annoying possi-bility. As the initial position of the agent s need not be at the open end of thechain, it is possible that from s the angle between the furthest seen clockwise and48counterclockwise vertices is not a right angle. However similar to the corner-radiusstrategy we can imagine replacing the edge(s) initially seen from s with a singleedge from s to the first corner in which the agent must look around. Thus whenthe agent determines the first circle center to generate its trajectory, the diameter ofthis circle is the length of the line segment from s to the first corner.We define the angle hull strategy as follows. Suppose the direction of traversalis counterclockwise. From the agent’s starting position s let c be the first cornerthe agent must look around. Replace all edges edges initially seen from s with thesingle edge from s to c. The agent then moves along circular arcs in the counter-clockwise direction such that at all points along its path it maintains a 90 degreefield of view between the furthest seen clockwise and counterclockwise vertices ofthe chain until the last edge is seen.Theorem 4.3.1. The angle hull strategy is pi/2-competitive for the convex chainproblem.Proof. Let |e1|, |e2|, . . . , |en| denote the lengths of the edges of the chain where sis located at the open endpoint of e1. We again partition the length of the shortestinspection path that sees the chain into the portion along the boundary of the chainand the portion off of the chain:|O| = |O‖|+ |O⊥| =u∑j=1|ej |+n−1∑j=u+1|ej | sinn−1∑i=jφjwhere edge eu is the last edge in which the optimal path remains on the boundaryof the chain.Let ai denote the ith circular arc generated by the angle hull strategy with cidenoting its center and di denoting its diameter. Let αi be the angle spanned by aisuch that its length is αidi. Note that this states the angle is measured not aroundcenter ci, but at the corner that the agent is currently attempting to look around;this entails that 0 < αi ≤ pi/2.Let Ei be the total length of the (consecutive) edges seen from arc ai. Clearlydi ≤ Ei. Further, let Aj be the total sum of angles αi where arc ai sees edge ej .With this notation, we can express an upper bound on the length of the angle hull49a1a2a3a4a5a6c1c2c3c4c5c6φ1φ2φ3φ4so3 o4Figure 4.5: An instance of the angle hull strategy. The agent on arc a2 seesboth endpoints of the subchain formed by edges e1 and e2. The circlecenter in which arc ai is generated from is a cross labelled ci. Theangles α3 and α4 correspond to the angles given by the light green anddark green shaded regions, and α5 and α6 the light purple and darkpurple shaded regions respectively. Note that A3 + A4 = φ3 + φ4 andA4 = φ4.strategy AAH as|AAH | =n−1∑i=1αidi ≤n−1∑i=1αiEi =n−1∑j=1|ej |Ajby rearranging terms.The angle hull path generated by this strategy crosses the extension of someedges twice; first when the edge becomes visible to the agent and second when theedge is no longer visible. For the remaining edges the angle hull path only crossestheir extensions once before the final edge of the chain is seen.Observe that edge eu is the last edge whose extension is crossed twice. Thisis true of the shortest inspection path since it leaves the boundary and follows50a straight line after traversing eu. The angle hull path starts at the same pointas the shortest inspection path, remains separated from the chain by the shortestinspection path, crosses extensions in the same order, and ends at the same pointon the extension of the final edge. Thus for all edges ej , 1 ≤ j ≤ u, the angle hullpath crosses the extension of ej twice and the sum of the angles that belong to ejis exactly pi/2. That is, Aj = pi/2.We now claim for edges ej , u < j ≤ n − 1, Aj = φj + φj+1 + . . . + φn−1.This follows as exactly the angles φj + . . . + φn−1 belong to edge ej , anglesφj+1 + . . .+ φn−1 to edge ej+1, and so on. Therefore we haven−1∑j=u+1|ej |Aj =n−1∑j=u+1|ej | (φj + . . .+ φn−1)With this the competitiveness of the angle hull strategy is clear as we have|AAH | ≤ pi2u∑j=1|ej |+n−1∑j=u+1|ej | (φj + . . .+ φn−1)≤ pi2 u∑j=1|ej |+n−1∑j=u+1|ej | sin (φj + . . .+ φn−1)≤ pi2|O|again by observing that for u < j ≤ n − 1, φj + . . . + φn−1 ≤ pi/2 and forx ∈ (0, pi/2), x ≤ pi/2 sin(x).Therefore by using the angle hull strategy in the two-sided search strategy, asdescribed in Section 4.2, Theorem 4.2.2 impliesTheorem 4.3.2. The two-sided, angle hull strategy for the convex polygon inspec-tion problem is 9pi/2-competitive.51saFigure 4.6: A three edge polygon in which the agent, following some strat-egy, takes an initial step in the wrong direction from s to a, then returnsto s. The agent then moves in the correct direction to inspect the finaledge. In red is the shortest inspection path with length  which can bearbitrary small for such polygons.4.4 A Lower Bound on the Length of the ShortestInspection PathIn Section 4.2 we presented the two-sided, C strategy for the convex polygon in-spection problem. This strategy required knowledge of a lower bound λ on thelength of the shortest inspection path which was used to determine the initial dis-tance the agent would traverse to search in one direction around the polygon.Without knowledge of such a lower bound the agent may initially traverse inthe wrong direction around the polygon a distance d then returns to s, where theoptimal path moves a very small distance,  d, in the other direction away from sto finish the inspection; see Figure 4.6. As  can be arbitrary small, the competitiveratio 2d+ can be unbounded. In such a scenario it would seem that the agentwould need to be content with perhaps not being competitive for all instances ofthe problem, yet satisfied with traveling small distances. For example, supposea step size of d = 1 was chosen. When  d (and thus the strategy is notcompetitive) the agent, which will traverse at most distance 2+ before completingthe inspection, may be content that its traversal is at most length two more than thelength of the shortest inspection path.Fortunately for the agent such a compromise does not need to be made. Fromits starting position s the agent sees some portion of the polygon before traversing.Using this information, the agent can infer a lower bound on the length of any52shortest inspection path which inspects the remainder of the polygon which can beused as its initial step size λ.Let S be the subchain of edges seen from the agent’s initial position at s. Leta and b be the open endpoints of S. To determine a lower bound on the length ofthe optimal path we return to the notion of scope defined by Tiktinsky et al. [22].The rays −→sa and −→sb (along with the line ab) define the unknown region in whichthe remaining edges lie. For all starting positions s, this region is unbounded, andany inspection path must close this region by first making these boundaries parallelto one another, then collapsing them such that the unknown region becomes empty(i.e. all edges are seen.)To determine a lower bound on the length of the shortest inspection path weask what is the shortest path from s that will make the boundaries of the unknownregion parallel. We determine such a quantity as follows. We cast a collection ofrays from s through a point p ∈ ab, where p walks from a to b. For each ray −→sp,let Ap and Bp be the lines parallel to −→sp that pass through a and b respectively; seeFigure 4.7. To make the boundaries parallel the agent needs to move from s to Apand Bp. As both must be reached the distance of traversal is at least the maximumof the two distances. Thus we are interested in minimizing this quantity over pointsp to determine a lower bound on the optimal:|O| ≥ minp∈abmax{d(s,Ap), d(s,Bp)}.where d(s, L) is the shortest distance from s to line L.Since max{d(s,Ap), d(s,Bp)} ≥ 12(d(s,Ap) + d(s,Bp)) and the latter termof the inequality is at least the distance between the two lines Ap and Bp, whichfor such rays is minimized when p = a or p = b, we have|O| ≥ minp∈{a,b}(d(Ap, Bp)2)where d(Ap, Bp) is the minimum distance between the two lines Ap and Bp. Notethat in the last inequality we only need to cast two rays and compute the corre-53absp2p1 = ap3 = bAp2Bp2Ap1Bp1Ap3Bp3Figure 4.7: Three rays through p1 = a, p2, and p3 = b. For each ray, thelines parallel to the ray are shown as dash dotted lines.sponding lines Aa and Bb for the two values of p. Therefore the agent can effi-ciently compute the lower bound.4.5 Extension: Constraints on Inspection AngleIn Section 3.5 we considered an additional constraint on how the agent could in-spect an edge. Namely an angle α is specified such that an agent can only inspect apoint x on an edge ei if the agent is positioned within the conic (inspection) regionwith apex x, interior angle 2α, and whose major axis is perpendicular to edge ei.If x is a vertex of the polygon, then the major axis may be perpendicular to anytangent at x and the inspection region is the union of all such cones. Such a con-straint prohibits the agent from viewing all points of an edge by simply reaching itsextension, instead forcing it to traverse across the inspection regions of all pointsof the edge.A natural question is can our results for the online version of the polygon in-spection problem be extended to this scenario; if the agent is aware of the angle54α, but not the polygon itself, is there a competitive strategy for the agent to see alledges for some starting position s? Note that we understand seeing and inspectingof an edge to be the same; the agent cannot first see the entirety of an edge, thenmove to inspect all points of the edge; both the detection of a point of the edge andthe inspection of that point happens simultaneously.We consider the following competitive strategy for the convex chain problemwith inspection angle α. Suppose the agent is located at a position s on the openendpoint of a convex chain, and let t be the opposite endpoint of the chain. Theshortest inspection path with inspection angle α is the shortest path from s to apoint on the boundary of IR(t). An agent seeking to inspect all edges of the poly-gon can find itself in one of two states. Either it knows the direction of an edge itis currently inspecting or it has reached a corner of the chain where the location ofthe next edge to inspect is unknown. We say that an agent is either in a translationstate or rotation state respectively.We define the perpendicular traversal strategy as follows. From s the agent,initially in a translation state, inspects edge e1 by traversing in a direction perpen-dicular to IR1R(x) for all x on e1. Let v1 denote the shared endpoint (corner) ofedges e1 and e2. The agent then enters a rotation state in which it follows a circulararc centered on v1 with radius r1 = |e1| cos(α) where α = pi/2−α until IR2R(v1)is reached and the direction of edge e2 is discovered. The agent again enters atranslation state and inspects e2 by moving from its current position in a directionperpendicular to IR2R(x) for all x on e2 until the next corner is discovered. Thisprocess is repeated until all n edges of the chain are fully seen; see Figure 4.8.Let APT denote the path resulting from the perpendicular traversal strategy.The overall length of APT can be expressed by summing over all lengths in whichthe agent is in either a translation or rotation state. Let ai denote the length corre-sponding to the perpendicular traversal that fully inspects edge ei for 1 ≤ i ≤ nand bi the length of the circular arc of traversal around vertex vi for 1 ≤ i ≤n − 1. Observe that ai = |ei| sin(α). For the arc length bi let ψi denote the an-gle by which the agent rotates and ri the distance the agent is away from vi sobi = ψiri = ψi cos(α)(|e1| + |e2| + . . . + |ei|), as the radius ri is the sum ofdistances the agent is away from each corner when it switches to a rotation statefrom a translation state, each of which contributes |ej | cos(α) for 1 ≤ j ≤ i.55a1b1a2b2a3b3a4b4a5e1e2 e3e4e5IR1R(v1)IR2R(v1)IR2R(v2)IR3R(v2)IR3R(v3)IR4R(v3)IR4R(v4)IR5R(v4) IR5R(v5)v1v2v3v4v5sψ1ψ2ψ3ψ4αFigure 4.8: In blue is the inspection path resulting from the perpendiculartraversal strategy with lengths ai and bi labelled. In red is the shortestinspection path for this chain. Notice the collection of right trianglesformed with base lengths of O.Therefore the total length of the perpendicular traversal strategy can be ex-pressed as|APT | =n−1∑i=1(ai + bi)+ an=n−1∑i=1(|ei| sin(α) + ψi cos(α)( i∑j=1|ej |))+ |en| sin(α)=n∑i=1|ei|(sin(α)+( n−1∑j=iψj)cos(α)).56We wish to relate the length of the perpendicular traversal strategy to that ofthe shortest inspection path O for the chain. To do so, we again partition O intotwo paths: the first part which lies on the boundary and the second which movestowards IRnR(vn) once a straight-line path is feasible. Let eu be the final edge thatis traversed by O. Then the length of O is|O| =u∑i=1|ei|+n∑i=u+1|ei| sin(α+n−1∑j=iψj)where the terms of the latter summation are base lengths of a collection of righttriangles; see Figure 4.8. The angle between the side length and the hypotenuse enof the last of these triangles is α since this is where the agent can first inspect thelast endpoint of en. For the triangle with hypotenuse ei, for u < i < n, this angleincreases by the angles the agent rotates ψn−1 + ψn−2 + · · · + ψi. Thus the baselength of the triangle with hypotenuse ei for u < i ≤ n is |ei| sin(α +∑n−1j=i ψj).Notice that the angle is always at most pi/2.To proceed we make use of the following lemma where we can imagine thatx = α and y =∑n−1j=i ψj .Lemma 4.5.1. For 0 ≤ x ≤ pi/2, 0 ≤ y ≤ pi/2 such that x + y ≤ pi/2, theinequality sin(x) + y cos(x) ≤ pi2 sin(x+ y) holds.Proof. We first show that the function f(x, y) = x + y−(sin(x) + y cos(x))isconvex on the domain and that this function’s minimum is 0. This entails sin(x) +y cos(x) ≤ x+ y.By taking partial derivatives of f we find∇f(x, y) =(1− cos(x) + y sin(x)1− cos(x)),∇2f(x, y) =(sin(x) + y cos(x) sin(x)cos(x) 0).57Observe that ∇2f(x, y) is positive semi-definite. Thus f is a convex functionfor x, y in the given domain.Setting∇f(x, y) = 0 we determine that x = 0 and y ∈ [0, pi/2]. Thus for suchy, f(0, y) = y − y = 0 and the minimum of f on the given domain is zero.Finally we use x + y ≤ pi/2 sin(x + y) for x + y ∈ [0, pi/2] to achieve thedesired inequality.We partition |APT | to match |O|, apply the above Lemma, and observe ψ1 +. . .+ ψn−1 ≤ 2pi by convexity of the chain to derive|APT | =u∑i=1|ei|(sin(α)+( n−1∑j=iψj)cos(α))+n∑i=u+1|ei|(sin(α)+( n−1∑j=iψj)cos(α))≤ (1 + 2pi)u∑i=1|ei|+ pi2n∑i=u+1|ei| sin(α+( n−1∑j=iψj))≤ (1 + 2pi)( u∑i=1|ei|+n∑i=u+1|ei| sin(α+( n−1∑j=iψj)))≤ (1 + 2pi)|O| ≈ 7.28|O|Thus we have,Theorem 4.5.2. For starting position s located at the open endpoint of the chainand inspection angleα, the perpendicular traversal strategy is (1+2pi)-competitivefor the convex polygon inspection problem with inspection angle α.For starting position s located off of the chain it remains to be shown if theperpendicular traversal strategy is competitive. Unlike the original problem, anonline strategy cannot replace the edges initially seen from s with a single edgefrom s to where the shortest inspection path contacts the boundary since it can’tnecessarily even “see” this point (i.e. s might lie outside of this point’s inspectionregion).58Chapter 5ConclusionIn this work we considered the convex polygon inspection problem where a mobileagent, initially positioned at a point s external to a convex polygon Q, must gen-erate an inspection path from s such that all points on the boundary of Q are seenfrom some point along the path. In Section 3.2 we defined the ways in which ashortest inspection path may contact an edge extension allowing the agent to fullysee the edge. In particular a reflecting contact corresponds to an agent changingits direction of traversal, and by Theorem 3.2.3 we determined that a shortest in-spection path will consist of at most one reflecting contact on its interior that mustoccur on an edge extension. A consequence of Theorem 3.2.3 allows for an effi-cient linear time algorithm to determine the shortest inspection path which sees allof the boundary of Q.We then considered two extensions of the convex polygon inspection problem:the addition of a terminal point where the path must end and a constraint on howa point on an edge is visible to the agent specified by an angle 0 ≤ α ≤ pi/2. Forthe former, in Section 3.4 Theorem 3.4.1 showed that the shortest inspection pathwith a specified terminal point will consist of at most two reflecting contacts on itsinterior. By similar methods to the original problem, one can determine the shortestinspection path from s to the terminal point by constructing a linear number ofshortest inspection paths and reporting the path of overall minimal length. Forthe latter problem Lemma 3.5.1 and Theorem 3.5.2 gave similar insights to thestructure of a shortest inspection path which would allow for an efficient algorithm59to determine such a path with inspection angle α. When α = pi/2 we have theoriginal polygon inspection problem in which the shortest inspection path consistsof at most one reflecting contact on its interior. A consequence of Theorem 3.5.2showed that a shortest inspection path with inspection angle α = 0 will containno reflecting contact on its interior. An interesting open question is: for whatinspection angles α does the shortest inspection path contain no reflecting contactfor any s and any polygon? Is there a value of α where there are two shortestinspection paths one with and one without a reflecting contact?We then considered an online version of the polygon inspection problem wherethe agent is not given knowledge of Q in advance, only that it is convex. Our mainresult was the two-sided, angle hull strategy for the agent to employ which seesall points on the boundary of Q by traversing a distance at most 4.5pi ≈ 14.14 thelength of the shortest inspection path that can be achieved when Q is known inadvanced, an improvement on recent work by [22]. This was a result of extendingthe work by Icking et al. [15, 16] from looking around a single corner to a sequenceof corners (a chain of edges) which originate from a convex polygon. Using sucha strategy to look around the polygon in one direction, we used this strategy tosearch in both directions, taking incremental steps until all the boundary is fullyseen. The manner in which the incremental steps are determined followed in thesame manner as the linear spiral search strategy for one dimensional search on aline (also known as the cow-paths problem.)Future work would include determining a lower bound on the competitive fac-tor that any competitive strategy for the convex polygon inspection problem mayachieve. Such an insight may also suggest a strategy that achieves such a com-petitive factor. Further, the angle hull strategy which looks around the polygon inone direction appears to be tight [14]. Thus by continuing with the paradigm de-scribed in Section 4.2 it seems one could only improve upon the competitive factorby employing a better strategy for searching both sides of the polygon.Finally in Section 4.5 we described the perpendicular traversal strategy for theonline version of convex chain problem when a constraint on the inspection angleis specified. Theorem 4.5.2 showed that this strategy is 1 + 2pi ≈ 7.28 competitiveif the starting location is the open endpoint of the chain. It remains to be shownthat the strategy is competitive for an arbitrary starting position that sees the first60endpoint of the chain. If so one would assume such a strategy could be used forthe convex polygon inspection problem with inspection angle α by employing adoubling search technique to search in both directions. The use of the perpen-dicular traversal strategy as a sub-strategy may result in a competitive factor of9(1+2pi) ≈ 65.55 by an analysis similar to that in Section 4.2. However one issueis the choice of an initial step size for the doubling search. When an inspectionangle α is specified, it is possible that the agent’s starting position only allows it tosee a single point of the polygon’s boundary. With only this information a lowerbound on the length of the shortest inspection path must be determined to use as astep size.61Bibliography[1] M. Abrahamsen, A. Adamaszek, and T. Miltzow. The art gallery problemis∃ -complete. In Proceedings of the 50th Annual ACM SIGACT Symposiumon Theory of Computing, pages 65–73, 2018. → page 3[2] R. A. Baeza-Yates, J. C. Culberson, and G. J. Rawlins. Searching in theplane. Information and Computation, 106(2):234–252, 1993. → pagesv, 7, 44[3] S. Carlsson, H. Jonsson, and B. J. Nilsson. Finding the shortest watchmanroute in a simple polygon. Discrete & Computational Geometry, 22(3):377–402, 1999. → page 13[4] W.-P. Chin and S. Ntafos. Optimum watchman routes. In Proceedings of theSecond Annual Symposium on Computational Geometry, pages 24–33,1986. → page 4[5] W.-P. Chin and S. Ntafos. Shortest watchman routes in simple polygons.Discrete & Computational Geometry, 6(1):9–31, 1991. → pages 4, 13[6] J. Czyzowicz, P. Egyed, H. Everett, D. Rappaport, T. Shermer, D. Souvaine,G. Toussaint, and J. Urrutia. The aquarium keeper’s problem. InProceedings of the second annual ACM-SIAM symposium on Discretealgorithms, pages 459–464, 1991. → page 21[7] R. Dorrigiv, A. Lo´pez-Ortiz, and S. Tawfik. Optimal average case strategyfor looking around a corner. In Proceedings of the 24th CanadianConference on Computational Geometry, pages 277–282, 2012. → page 8[8] M. Dror, A. Efrat, A. Lubiw, and J. S. Mitchell. Touring a sequence ofpolygons. In Proceedings of the 35th ACM Symposium on the Theory ofComputing, pages 473–482, 2003. → pages 4, 562[9] A. Dumitrescu and C. D. To´th. Watchman tours for polygons with holes.Computational Geometry, 45(7):326–333, 2012. → page 5[10] S. Fisk et al. A short proof of chva´tal’s watchman theorem. Journal ofCombinatorial Theory, 1978. → page 3[11] S. Gal. Minimax solutions for linear search problems. SIAM Journal onApplied Mathematics, 27(1):17–30, 1974. → page 7[12] S. K. Ghosh and R. Klein. Online algorithms for searching and explorationin the plane. Computer Science Review, 4(4):189–201, 2010. → page 7[13] S. Hildebrandt and A. Tromba. Mathematics and Optimal Form. W. H.Freeman & Co, 1985. → page 21[14] F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. The polygon explorationproblem ii: The angle hull. Technical Report 245, Department of ComputerScience, FernUniversita¨t Hagen, 1998. → pages 47, 48, 60[15] C. Icking, R. Klein, and L. Ma. How to look around a corner. InProceedings of the 5th Canadian Conference on Computational Geometry,pages 443–448. University of Waterloo, 1993. → page 60[16] C. Icking, R. Klein, and L. Ma. An optimal competitive strategy for lookingaround a corner. Technical Report 167, Department of Computer Science,FernUniversita¨t Hagen, 1994. → pages v, 2, 8, 38, 40, 60[17] D. Lee and A. Lin. Computational complexity of art gallery problems. IEEETransactions on Information Theory, 32(2):276–282, 1986. → page 3[18] S. Ntafos and L. Gewali. External watchman routes. The Visual Computer,10(8):474–483, 1994. → page 6[19] J. O’Rourke. Art Gallery Theorems and Algorithms. Oxford UniversityPress, 1987. → pages 3, 4[20] J. O’Rourke and K. Supowit. Some np-hard polygon decompositionproblems. IEEE Transactions on Information Theory, 29(2):181–190, 1983.→ page 3[21] X. Tan, T. Hirata, and Y. Inagaki. Corrigendum to “An IncrementalAlgorithm for Constructing Shortest Watchman Routes”. InternationalJournal of Computational Geometry & Applications, 9(03):319–323, 1999.→ page 563[22] E. Tiktinsky, S. Gul, S. Shamshanov, and R. Cohen. Online explorationoutside a convex obstacle. arXiv preprint arXiv:1807.02773, 2018. → pagesiv, 2, 8, 9, 11, 53, 60[23] G. T. Toussaint. Solving geometric problems with the rotating calipers. InProc. IEEE Melecon, volume 83, page A10, 1983. → page 2064
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
On competitive strategies for external exploration of a convex polygon
Text