Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Bounded-curvature motion planning amid polygonal obstacles Backer, Jonathan 2009

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
24-ubc_2009_spring_jonathan_backer.pdf [ 1001.44kB ]
Metadata
JSON: 24-1.0051257.json
JSON-LD: 24-1.0051257-ld.json
RDF/XML (Pretty): 24-1.0051257-rdf.xml
RDF/JSON: 24-1.0051257-rdf.json
Turtle: 24-1.0051257-turtle.txt
N-Triples: 24-1.0051257-rdf-ntriples.txt
Original Record: 24-1.0051257-source.json
Full Text
24-1.0051257-fulltext.txt
Citation
24-1.0051257.ris

Full Text

Bounded-Curvature Motion Planning amid Polygonal Obsta
les by Jonathan Ba
ker a thesis submitted in partial fulfillment of the requirements for the degree of Do
tor of Philosophy in the fa
ulty of graduate studies (Computer S
ien
e) University of British Columbia (Van
ouver) February 2009 
© Jonathan Ba
ker, 2009 Abstra
t We 
onsider the problem of nding a bounded-
urvature path in the plane from one 
onguration αs to another 
onguration αt that avoids the interior of a set of polygonal obsta
les E . We 
all any su
h path from αs to αt a feasible path. In this thesis, we develop algorithms to nd feasible paths that have expli
it guarantees on when they will return a feasible path. We phrase our guarantees and run time analysis in terms of the 
omplexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, whi
h is parti
ularly desirable be
ause there are no known bounds on the solution 
omplexity amid arbitrary polygonal environments. Our rst major result is an algorithm that given E , αs, αt, and a positive integer k either (i) veries that every feasible path has a des
riptive 
omplexity greater than k or (ii) outputs a feasible path. The run time of this algorithm is bounded by a polynomial in n (the total number of obsta
le verti
es in E), m (the bit pre
ision of the input), and k. This result 
omplements earlier work by Fortune and Wilfong [17℄: their algorithm 
onsiders paths of arbitrary des
riptive 
omplexity (it has no dependen
e on k), but it never outputs a path, just whether or not a feasible path exists. Our se
ond major result is an algorithm that given E , αs, αt, a length λ, and an approximation fa
tor ε, either (i) veries that every feasible path has length greater than λ or (ii) 
onstru
ts a feasible path that is at most (1 + ε) times longer than the shortest feasible path. The run time of this algorithm is bounded by a polynomial in n, m, ε−1, and λ. This algorithm is the result of applying the te
hniques developed earlier in our thesis to the previous approximation approa
hes [18, 3℄. A short
oming of these prior approximation algorithms is that they only sear
h a spe
ial 
lass of feasible paths. This restri
tion implies that the path that they return may be arbitrarily longer than the shortest path. Our algorithm returns a true approximation be
ause we sear
h for arbitrary shortest paths. ii Contents Abstra
t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v A
knowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introdu
tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Statement of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Paths in Free Spa
e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Paths Amid Obsta
les . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Fortune and Wilfong Normal Form . . . . . . . . . . . . . . . . . . . . 24 3.2 Combinatorial Augmentation . . . . . . . . . . . . . . . . . . . . . . . 27 4 Testing Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1 Exhaustive Sear
h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Redundan
y Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5 Eliminating Redundan
y . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.1 Filtering with Walls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Corner to Corner Extensions . . . . . . . . . . . . . . . . . . . . . . . . 43 5.3 Bounds on the Run Time . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6 Shortest Bounded-Curvature Path Approximation . . . . . . . . . 56 6.1 Path Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.2 Systemati
 Sear
h for Shortest ε-Dis
rete Paths . . . . . . . . . . . . . 61 6.3 Redundan
y Among Conta
t Congurations . . . . . . . . . . . . . . . 62 7 Con
lusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 iii Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 A Jumps between Corners . . . . . . . . . . . . . . . . . . . . . . . . . . 71 A.1 Sides of a Jump . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 A.2 Non-Crossing Condition . . . . . . . . . . . . . . . . . . . . . . . . . . 73 B Links between Corners . . . . . . . . . . . . . . . . . . . . . . . . . . 80 B.1 Link Monotoni
ity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 B.2 Non-Crossing Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.3 Number of Homotopy Classes . . . . . . . . . . . . . . . . . . . . . . . 86 C Convergen
e to a Fixed-Point . . . . . . . . . . . . . . . . . . . . . . 87 C.1 Forward Iteration (∆ < 2) . . . . . . . . . . . . . . . . . . . . . . . . . 87 C.2 Forward Iteration (∆ > 2) . . . . . . . . . . . . . . . . . . . . . . . . . 95 C.3 Ba
kward Iteration (∆ ≤ 2) . . . . . . . . . . . . . . . . . . . . . . . . 97 C.4 Ba
kward Iteration(∆ ≥ 2) . . . . . . . . . . . . . . . . . . . . . . . . . 102 iv List of Figures 1.1 Visualisation of the bounded 
urvature 
onstraint. . . . . . . . . . . . . 3 1.2 Example problem instan
es. . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Paths are wedged between 
ones. . . . . . . . . . . . . . . . . . . . . . 9 2.2 Length redu
ing deformations. . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Shortest un
onstrained path amid polyhedra. . . . . . . . . . . . . . . . 12 2.4 Rea
hable intervals of obsta
le 
onta
t. . . . . . . . . . . . . . . . . . . 14 2.5 Some moderate obsta
les. . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 A oating pair of C-segments. . . . . . . . . . . . . . . . . . . . . . . . 16 2.7 A 
orridor and its redu
ed 
orridor. . . . . . . . . . . . . . . . . . . . . 18 2.8 A robot with a turning radius of one 
annot traverse this 
orridor. . . . 18 2.9 Environment 
onta
ts that not ε robust. . . . . . . . . . . . . . . . . . 21 3.1 Deformations used in FW normalisation. . . . . . . . . . . . . . . . . . 24 3.2 Representing a FW-normal path as a sequen
e of jumps. . . . . . . . . 25 3.3 Observations leading to our jump representation. . . . . . . . . . . . . 26 3.4 Ea
h 
onta
t 
onguration has one degree of freedom. . . . . . . . . . . 28 3.5 We introdu
e 
onstraints as we roll a 
onguration. . . . . . . . . . . . 30 3.6 A 
onguration be
omes moored by rolling it. . . . . . . . . . . . . . . 31 4.1 Linkages and an
hor graphs. . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Algorithm that exhaustively sear
hes for linkages. . . . . . . . . . . . . 37 4.3 One 
hain dire
tly rea
hes another. . . . . . . . . . . . . . . . . . . . . 38 4.4 Filtering 
ongurations before propagation. . . . . . . . . . . . . . . . . 39 5.1 Jump spe
tra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.2 Our subproblems guarantee feasibility. . . . . . . . . . . . . . . . . . . 45 5.3 Only one 
onguration θ 
an rea
h ψ. . . . . . . . . . . . . . . . . . . . 46 5.4 The 
ongurations that 
an be rea
hed by a jump. . . . . . . . . . . . 48 5.5 Singular jump spe
tra. . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.6 Using symmetries to simplify the 
onstru
tion of 〈Ψi〉. . . . . . . . . . 49 5.7 Generating a 
ontiguous 
over. . . . . . . . . . . . . . . . . . . . . . . . 50 5.8 Ba
kwards iteration overlaps forwards iteration. . . . . . . . . . . . . . 51 6.1 Conta
t 
onguration degree of freedom. . . . . . . . . . . . . . . . . . 58 v 6.2 Pro
edure to 
onstru
t short linkages. . . . . . . . . . . . . . . . . . . . 61 6.3 Pro
edure to 
onstru
t short viable linkages. . . . . . . . . . . . . . . . 63 A.1 Jumps from F to G with L-segments pointing in one xed dire
tion. . . 72 A.2 L-segments are 
ontained in R. . . . . . . . . . . . . . . . . . . . . . . 73 A.3 Points rea
hed by a jump starting with a 
lo
kwise oriented C-segment. 73 A.4 Segments of the same type do not 
ross. . . . . . . . . . . . . . . . . . 74 A.5 Jumps from c to O starting with a 
lo
kwise C-segment. . . . . . . . . 74 A.6 Earlier C-segment does not 
ross later L-segment. . . . . . . . . . . . . 75 A.7 Range of jumps from c to O starting with a 
ounter
lo
kwise C-segment. 76 A.8 Later C-segment does not 
ross earlier L-segment. . . . . . . . . . . . . 77 A.9 Earlier C-segment does not 
ross later L-segment . . . . . . . . . . . . 77 A.10 Lo
us of points rea
hing a 
onguration φ. . . . . . . . . . . . . . . . . 78 A.11 The jump S 
erties that J1 and J2 do not 
ross. . . . . . . . . . . . . 79 A.12 Jumps to the same 
onguration φ do not 
ross. . . . . . . . . . . . . . 79 B.1 A range of C−L0C+ stru
ture links from F to G. . . . . . . . . . . . . 80 B.2 Same underlying 
ir
le 
entres. . . . . . . . . . . . . . . . . . . . . . . 81 B.3 Monotoni
ity of links with stru
ture C0LC + . . . . . . . . . . . . . . . . 81 B.4 Monotoni
ity of links with stru
ture C−pi LC + . . . . . . . . . . . . . . . 82 B.5 Arbitrary quadrilateral expressed as ve
tors and angles. . . . . . . . . . 83 B.6 CL0C-link monotoni
ity. . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.7 Neighbours do not 
ross. . . . . . . . . . . . . . . . . . . . . . . . . . . 86 C.1 Forward iteration approximation. . . . . . . . . . . . . . . . . . . . . . 87 C.2 Underestimate forward iteration when ∆ ≤ 2. . . . . . . . . . . . . . . 95 C.3 Early termination when ∆ > 2. . . . . . . . . . . . . . . . . . . . . . . 96 C.4 Underestimate of ba
kward iteration. . . . . . . . . . . . . . . . . . . . 97 C.5 The position of L for ∆ > 2 is the same as its position for ∆ = 2. . . . 102 vi A
knowledgements Foremost, I would like to thank my supervisor, David Kirkpatri
k, for all of his support over the years. He generously shared his immense experien
e as a resear
her, writer, and tea
her, whi
h fostered my a
ademi
 and personal growth. This thesis is extremely te
hni
al in several pla
es, and David was an invaluable guide when I be
ame lost be
ause I 
ould no longer see the forest for all of the trees. Where my arguments are elegant, it is be
ause David knew that they 
ould be. Where they are ugly, it is be
ause I 
ould see no other way. In addition to David, I want to thank two other members of my PhD 
ommittee: Will Evans and Ian Mit
hell. Will was an en
ouraging sounding board, and Ian looked at my thesis through the eyes of a pra
titioner (even though this is a very theoreti
al thesis). On a personal note, I 
ould not have nished this thesis without the emotional support (and unending patien
e) of my wife, Robin. I also want to thank my parents: they always en
ouraged me to satisfy my 
uriousity, and they taught me the value of hard work through their example. vii Chapter 1 Introdu
tion The types of problems that we address in this thesis arise when planning the motion of robots. To see some of the issues involved, 
onsider two dierent problems: the exploration of the surfa
e of planets and the assembly of 
ars in fa
tories. When ex- ploring new environments, the result of a robot's a
tion may be unpredi
table (we only know the probability of various out
omes) and the environment may be 
hanging or unknown. In industrial settings, we 
an engineer the problem around the solution. Hen
e, the opposite is often true: the result of a robot's a
tion is predi
table and the environment is stati
 and known in great detail. However, even in this ideal setting, there remain two types of di
ulties in planning motion: the 
urse of dimensionality and kinemati
 
onstraints. Intuitively, the former means that the relation between a robot and its environment is 
ompli
ated, and the latter means that slightly 
hanging the relation between a robot and its environment may require a 
ompli
ated a
tion (e.g. moving a 
ar slightly 
loser to the 
urb when parallel parking). Kinemati
 
on- straints are 
lassied as holonomi
 or nonholonomi
. There are standard te
hniques to deal with holonomi
 
onstraints, but the same is not true of nonholonomi
 
onstraints. The fo
us of our resear
h is how to deal with a spe
i
 type of nonholonomi
 
onstraint. We now 
onsider the problem of moving a box via rigid motions to illustrate the dieren
e between holonomi
 and nonholonomi
 
onstraints, (see [20℄ for a more pre
ise denition). Note that we 
an spe
ify the pla
ement of the box with three spatial parameters (one for ea
h 
oordinate axis x, y, and z) and three angular parameters (yaw, pit
h, and roll). Hen
e, the spa
e of all possible 
ongurations is six dimensional. Without any kinemati
 
onstraints, we 
an independent translate and rotate the box. More spe
i
ally, there are no restri
tions on the the velo
ity of the box in any dimension of its 
onguration spa
e (spatial or angular). Suppose that we want the box to slide along the surfa
e of a planet. We 
an model this restri
tion by insisting that the 
entre of one side of the box (the bottom) always tou
hes the outside of a large sphere (the planet). This restri
ts the pla
ement of the box to a three-dimensional subspa
e of its six-dimensional 
onguration spa
e. To see this, note that the pla
ement of the box is spe
ied by the point where the box tou
hes the sphere and its rotation about the ve
tor normal to the point of 
onta
t. 1 Although the pla
ement of the box is more restri
ted, the box still has quite a bit of freedom to move. In a three-dimensional frame of referen
e just des
ribed (relative to the sphere), the box 
an translate and rotate independently. More spe
i
ally, there are no restri
tions on the box's velo
ity in any dimension (spatial and angular) in the appropriate frame of referen
e. Intuitively, this is why restri
ting the box to the surfa
e of a sphere is 
onsidered a holonomi
 
onstraint. Now suppose that we want the box to move with a bounded turning radius like an automobile. To do this, we designate one side of the box as its front and insist that whenever the box translates, it moves in the dire
tion of the front or the dire
tion opposite the front. As the box moves, we limit how qui
kly it rotates relative to the distan
e travelled. Spe
i
ally, let s1 and s2 be any two pla
ements of the box. If the box travels ℓ units from s1 to s2 (the length of the 
urve tra
ed by the point of 
onta
t), we insist that the dieren
e in orientation from s1 to s2 is at most ℓ radians. Note that the spa
e of rea
hable pla
ements is exa
tly the same as it was before: we 
an rea
h any position and orientation on the sphere by moving far enough. What 
hanged is that we 
annot 
hange our position and orientation independently. More spe
i
ally, there are restri
tions on the box's velo
ity (spatial and angular). This is why restri
ting the turning radius is a nonholonomi
 
onstraint. The fo
us of this thesis is on 
ompleteness: nding a path, whenever one exists. To a
hieve this property, we must sometimes nd paths that are unsuitable for real-world robots be
ause they are either too di
ult or too 
ompli
ated for a robot to follow. So although our problems are motivated by real-world settings, their solutions are of more theoreti
al interest than pra
ti
al interest. Realisti
ally, we probably want to satisfy a dierent notion of 
ompleteness: nding a pra
ti
al path, whenever a pra
ti
al path exists. We hope that some of the te
hniques developed in this thesis may be used to a
hieve dierent notions of 
ompleteness as well. In this thesis, we adopt the algebrai
 model of 
omputation, where real numbers are the data primitive and arithmeti
 operations (+, −, ×, /, and √ ) take 
onstant time. This is distin
t from the bit model of 
omputation, where bits are the data primitive and boolean operations take 
onstant time. We use the algebrai
 model of 
omputation to simplify our analysis. This is quite 
ommon in the literature. We mention of use of the algebrai
 model now, be
ause it is another way in whi
h our results are theoreti
al. Converting our algorithms to the bit model of 
omputation probably 
annot be done in a straightforward manner. In order to a
hieve 
ompleteness, our algorithms 
onsider paths whose natural des
ription (in terms of planar 
oordinates) 
ould require a large number of bits in the bit model. That is, we doubt the one 
an dire
tly substitute approximate arithmeti
 (e.g. oating-point representation) for exa
t arithmeti
. However, we will argue that all the paths that we 
onsider have a su

in
t 
ombinatorial des
ription. So, it may be possible to use approximate arithmeti
 in a 
lever manner. In re
ognition of the theoreti
al nature of our work, we make no eort to optimise the performan
e of our algorithms (we are satised with polynomial bounds). This allows us to fo
us more on te
hnique and less on analysis (whi
h is already quite in- 2 volved in pla
es). This attention to te
hnique is important be
ause our te
hniques may have broader appli
ations. Spe
i
ally, we develop two general te
hniques to e
iently determine if a path exists: a dis
retisation of the path spa
e and a method pruning the sear
h for a path without sa
ri
ing 
ompleteness. The approximation results 
ontained in this thesis are a se
ond appli
ation of these two te
hniques. 1.1 Statement of Results The problem motivating our resear
h is moving a 
ar-like robot from one 
onguration (position and orientation) to another while avoiding obsta
les. To permit rigorous analysis, we restri
t our attention to a simplied setting: the robot is a point that only moves forward and it must avoid polygonal obsta
les in the two-dimensional plane. The restri
tion to forward motion is 
ommon. Intuitively, the problem with reversals is easier be
ause a point robot 
an turn sharply (on a dime) by making arbitrarily many reversals. We rst formalise what we mean by 
ar-like robot. Let X(s) : ℜ → ℜ2 be a dierentiable 
urve tra
ed by the point robot. We assume that X(s) is parameterised by ar
 length. We say that X has bounded 
urvature if there exists a 
onstant R (the smallest allowed radius of 
urvature) su
h that ∥∥∥dX ds (s1)− dXds (s2) ∥∥∥ ≤ R−1 |s1 − s2|, for every s1 and s2. A geometri
 interpretation of this denition is that a path has bounded 
urvature if every point on the path 
an be wedged between two 
ir
les of radius R lo
ally (see Figure 1.1). The robot 
an only move forward lo
ally be
ause the bounded-
urvature restri
tion limits how mu
h it 
an turn relative to the distan
e that it travels. Hen
e, the instantaneous 
onguration of a robot tra
ing su
h a path both its position and dire
tion in whi
h it 
an move. Like many of the bounded-
urvature results reported in the literature, we assume without loss of generality that R = 1 by suitable s
aling of the environment. Figure 1.1: Visualisation of the bounded 
urvature 
onstraint. A problem instan
e 
onsists of a sour
e 
onguration αs (the initial position and orientation of the robot), a target 
onguration αt (the destination position and orien- tation of the robot), and a set of obsta
les E to avoid (see Figure 1.2(a)). A solution to problem instan
e is a bounded-
urvature path from αs to αt that does not 
ross the interior of any obsta
le. In bounded-
urvature motion planning, we must sometimes follow a long path in order to slightly 
hange our orientation. For example, in Figure 1.2(b) the robot must 3 loop around an obsta
le in order to arrive at the same point with a slightly dierent orientation. The algorithmi
 results in bounded-
urvature motion planning handle this potential 
ompli
ation in two dierent ways. One result 
onsiders paths with an arbitrary amount of looping, but it runs in exponential time [17℄. Other results limit the degree of looping and run in polynomially bounded time. The approa
h to limiting the looping is often indire
t: by restri
ting the 
lass of obsta
les [2, 10, 1, 8℄ or restri
ting the type of paths that are found [18, 3℄. The results in this thesis are dierent in that they take a parameter (k and λ below) that dire
tly limits the amount of looping that we will 
onsider. αs αt (a) A problem instan
e and one solution. αs αt (b) A long path may be required to slightly 
hange the robot's orientation. Figure 1.2: Example problem instan
es. Our resear
h fo
uses on nding bounded-
urvature paths amid polygonal obsta
les. To distinguish them from graph-theoreti
 terms, we refer to obsta
le fa
es as walls (not edges) and the points where walls meet as 
orners (not verti
es). We assume that these obsta
les of E are disjoint and that an obsta
le does not interse
t itself. This is a modest restri
tion be
ause it is possible to prepro
ess the environment to make this assumption hold. The ee
t of this prepro
essing is at most a polynomially bounded in
rease in the 
omplexity of the environment. As in other bounded-
urvature results, we let n represent the number of 
orners in E . In this setting, the number n is an adequate measure the 
omplexity of E be
ause the total number of walls and 
orners is O(n) by Euler's formula. For purposes of analysis, we make a further assumption about the input: we assume that a problem instan
e is represented with m bits of pre
ision. Spe
i
ally, we insist that ea
h real parameter of the problem instan
e (su
h as a 
orner 
oordinate or a 
oordinate of a dire
tion ve
tor of αs) is represented as the ratio of two integers with magnitude at most 2m. Similar assumptions are made in other results in the eld [21, 17℄. Like the authors of these other results, we use this assumption to bound how dierent two distin
t things must be. For example, under this assumption two distin
t 
orners must be at least 2−O(m) and at most 2O(m) apart. The rst main result of this thesis was presented at the 23rd Annual Symposium on Computational Geometry [5℄. It is an algorithm that given E , αs, αt, and a positive integer k either (i) veries that every feasible path has a des
riptive 
omplexity greater 4 than k or (ii) 
onstru
ts a feasible path whose des
riptive 
omplexity is bounded by a polynomial in k. The run time of this algorithm is polynomially bounded in n, m, and k (a loose bound of O(n29k2(m+ nk)3) is presented in Se
tion 5.3). This result diers from the prior feasibility result [17℄ in two respe
ts: our algorithm runs in polynomially bounded time, whereas the previous algorithm takes exponential time; moreover, our result returns a path when a path is found whereas the prior result just indi
ates that a path exists. The se
ond main result of this thesis was presented at the 19th International Sym- posium on Algorithms and Computation [6℄. It is an algorithm that given E , αs, αt, a length λ, and an approximation fa
tor ε, either (i) veries that every feasible path has length greater than λ or (ii) 
onstru
ts a feasible path that is at most (1 + ε) times longer than the shortest feasible path. The run time of this algorithm is polynomially bounded in n, m, ε−1, and λ. Whereas our new result nds an approximation to the shortest path, the previous approximation results nd an approximation to the shortest ε-robust path [18, 3℄. We formally dene what it means for a path to be ε-robust in the next 
hapter, where we dis
uss the prior approximation results. Intuitively, a path Π is ε-robust, if Π 
an be deformed at ea
h point where Π tou
hes the environment by at least ε without making Π infeasible. The restri
tion to approximating an ε-robust path is substantial for two reasons. First, we 
an 
onstru
t instan
es where the shortest path is arbitrarily shorter than the shortest ε-robust path. In su
h 
ases, our new result will nd an approximation to the shortest path, but the previous approximation results will not. Se
ond, sometimes the only feasible paths are only ε-robust very small ε. In parti
ular, it was shown that nding a shortest bounded-
urvature path is NP-hard via redu
tion from 3SAT [23℄. All of the feasible paths in a problem instan
e that results from the polynomial time transformation of an instan
e of 3SAT are 2−Ω(n)-robust. In this 
ase, our approximation algorithm will nd a path in polynomially bounded time (all of the paths have length O(n)), but the previous approximation results may require exponential time to guarantee that they will nd a path. 1.2 Overview In the next 
hapter, we review many results related to our resear
h. A 
ore result is that every shortest bounded-
urvature path amid polygonal obsta
les is made of ar
s of unit-radius 
ir
les and straight-line segments [16, 18℄. We 
all any bounded- 
urvature path 
omposed of su
h ar
s and straight-line segments a Dubins path. This notion is important be
ause it often su
es to nd a Dubins path to solve a problem. Spe
i
ally, all of the bounded-
urvature motion planning algorithms in the literature look for a Dubins path. In the third 
hapter, we present a new normal form for bounded-
urvature paths. Every path in this normal form has a 
ombinatorial des
ription. Hen
e, the set of normal paths 
an be systemati
ally enumerated. Part of our analysis bounds how mu
h more 
ompli
ated a Dubins path be
omes by normalising it. To be more spe
i
, 5 let the intri
a
y of a Dubins path be the number of dierent segments of whi
h it is 
omposed. The intri
a
y of a path is a measure of its des
riptive 
omplexity be
ause ea
h path segment 
an be des
ribed by a 
onstant number of real numbers. We prove that if there is a Dubins path of intri
a
y k, then there is a normal path of intri
a
y at most O(nk + n3). In the fourth 
hapter, we present one way of exhaustively sear
hing for a path. The time that it takes to nd a parti
ular normal path is a fun
tion its intri
a
y. This is why the previous 
hapter's bound on the in
rease in intri
a
y is important: if there is a Dubin's path Π of intri
a
y k, then there exists a normal path Π′ of intri
a
y at most O(nk + n3). However, this exhaustive sear
h 
ould take time that is exponential in the intri
a
y of the path for whi
h we are looking, in the worst 
ase. So we show how to prune the sear
h. The major result of this 
hapter is that pruning does not sa
ri
e 
ompleteness. That is, although our sear
h may not nd Π′, it will nd a path Π′′ whose intri
a
y is roughly at most a 
onstant fa
tor greater than Π′. That is, the intri
a
y of Π′′ is also O(nk+n3). This is important be
ause the run time of the pruned sear
h still depends on the intri
a
y of the path Π′′ for whi
h we are sear
hing. In the fth 
hapter, we des
ribe the details of pruning. The pruning algorithms are straightforward and obviously take time that is polynomial in the size of the set that they prune. However, the proofs that they are 
orre
t (do not prune too mu
h) and return a polynomially bounded set are te
hni
al. The most te
hni
al of these details that are isolated in separate appendi
es: the rst and se
ond appendi
es analyse when two short, simple, bounded-
urvature paths do not 
ross; the third appendix analyses what one short, simple, bounded-
urvature path 
an rea
h. In the sixth 
hapter, we apply the te
hniques that we developed in the previous 
hapters to the problem of nding a feasible path that is not mu
h longer than the shortest feasible path. Again, intri
a
y plays a 
entral role but its use is indire
t. In this setting, we are looking for the shortest path Π with length less than λ. Given λ, we are able to obtain an upper bound k on the intri
a
y of Π. We argue that in order to approximate Π, it su
es to nd a path Π′ whose intri
a
y is polynomial in k. As before, it su
es to sear
h for paths of bounded intri
a
y. Unlike before, we 
annot stop as soon as we nd a path be
ause we want to nd a good approximation to the shortest path. To elaborate, in the worst 
ase, we must 
onsider all paths with intri
a
y below a 
ertain threshold in order to verify that the path that we have found is in fa
t a good approximation. In the seventh 
hapter, we 
on
lude with dire
tions for future resear
h. 6 Chapter 2 Literature Review The problems that we dis
uss in this 
hapter are 
losely related to bounded-
urvature motion planning. For a mu
h broader survey of motion planning from a theoreti
al perspe
tive, we dire
t the reader to an ex
ellent survey by Sharir [27℄. In all the problems dis
ussed in this 
hapter, we want to 
ontinuously move a point robot from a start 
onguration to a terminal 
onguration while avoiding the interior of stationary obsta
les. These problems dier in the type of obsta
les to avoid, the type of 
onstraints that are pla
ed on the motion, and how (or whether) the motion should be optimised. We say that a path is feasible if it begins at the start 
onguration, ends at the terminal 
onguration, satises the appropriate motion 
onstraints, and does not interse
t the interior of any obsta
le. We note that a feasible path 
an tou
h an obsta
le's boundary, whi
h is typi
al of optimal paths. In this 
hapter, we 
onsider a motion 
onstraint that is dierent from the bounded 
urvature 
onstraint: we say that the motion of a point satises the kinodynami
 
on- straint if (a) the magnitude of the point's velo
ity never ex
eeds a 
onstant and (b) the magnitude of the point's a

eleration never ex
eeds a 
onstant. By appropriate spatial and temporal s
aling, we 
an assume without loss of generality that these limiting 
on- stants are one [23℄. Noti
e that the bounded-
urvature 
onstraint is more restri
tive than the kinodynami
 
onstraint: a point robot 
an follow a bounded-
urvature path with unit speed (only the dire
tion of the velo
ity varies) without the magnitude of the a

eleration ever ex
eeding one (the dire
tion of the a

eleration is always orthogonal to the velo
ity). In the kinodynami
 setting, a point robot's instantaneous 
ongura- tion is its position and its velo
ity. As the speed of the robot 
an 
hange over time, the literature 
learly distinguishes between the path tra
ed by a robot and the robot's traje
tory : a des
ription of its 
onguration at any point in time. To illustrate the dieren
e between these two 
on
epts, note that two dierent traje
tories may tra
e the same path. In the kinodynami
 setting, the ee
t of the motion 
onstraint is weak- ened by travelling slowing: a robot 
an tra
e (almost) any 
ontinuous path by moving arbitrarily slowly. Hen
e, the kinodynami
 motion planning literature fo
uses on nd- ing the qui
kest traje
tory, unlike the bounded-
urvature literature whi
h looks for the shortest path. The kinodynami
 motion planning problem is investigated under both 7 the L2 norm (Eu
lidean norm) and the L∞ norm (supremum, uniform, or Chebyshev norm). Although the L2 norm is arguably more interesting, the L∞ norm is analyti
ally simpler. 2.1 Paths in Free Spa
e Finding a shortest path or qui
kest traje
tory are goals whi
h further restri
t the feasible solutions to a parti
ular problem that we 
onsider. Optimal solutions are rst studied in the absen
e of obsta
les, where the motion 
onstraint is the only 
on
ern. Typi
ally, the analysis results in a set of ne
essary 
onditions that optimal solutions must satisfy. We adopt the terminology found in other results in the eld and 
all solutions that satisfy these 
riteria 
anoni
al [18, 12, 3, 25℄. To 
larify, in the absen
e of obsta
les, every optimal solution is 
anoni
al but a 
anoni
al solution may be suboptimal be
ause it only satises ne
essary (not su
ient) 
onditions. Canoni
al solutions are important be
ause we need only 
onsider 
anoni
al solutions when sear
hing for an optimal solution: in free spa
e, every optimal solution is 
anoni
al, and amid obsta
les, an optimal solution is typi
ally a sequen
e of 
anoni
al solutions to subproblems. Canny et al. des
ribe the kinodynami
 qui
kest traje
tory under the L∞ norm [12℄. This norm is spe
ial be
ause the d-dimensions are de
oupled. Spe
i
ally, a traje
tory is kinodynami
 if and only if ea
h of its one-dimensional proje
tions is kinodynami
. Moreover, a qui
kest traje
tory 
an be 
omposed of qui
kest one-dimensional traje
to- ries (if qui
kest traje
tories in dierent dimensions take dierent times, gaps must be inserted to make them all take the same time). Hen
e, the 
hara
terisation of kinody- nami
 qui
kest traje
tories under the L∞ norm redu
es to the one dimensional 
ase. Qui
kest traje
tories in one dimension a

elerate as fast as possible towards the goal and de
elerate as fast as possible, when they must, to avoid overshooting the target. Despite the involved 
ase analysis, this strategy 
an be 
omputed qui
kly by solving quadrati
 equations. Dubins shows that shortest bounded-
urvature paths belong to a small set [16℄. He rst observes that a shortest path is made of a nite sequen
e of line segments (L-segments) and ar
s of unit-radius 
ir
les (C-segments). His argument is that short subpaths are sandwi
hed between two 
ones originating from the sour
e 
onguration and destination 
onguration of the subpath; the shortest path between those two 
ongurations uses C-segments from the 
ones and a bitangential L-segment (see Fig- ure 2.1). Ea
h subpath of a path must be optimal, whi
h proves that a shortest path is 
omposed of C- and L-segments. We 
all any dierentiable bounded-
urvature path 
omposed of C- and L-segments Dubins normal. The stru
ture of a Dubins path is the sequen
e of segment types of whi
h it is 
omposed, denoted by a string in {C,L}∗. The intri
a
y of a Dubins path is its total number of path segments. We 
hoose this parti
ular measure of the des
riptive 
omplexity of a path be
ause the size of a natural representation of a Dubins normal path is proportional to its intri
a
y. Note that in general, the intri
a
y and length of 8 Figure 2.1: Short subpaths (bla
k) are 
ontained between 
ones (dotted) emanating from the endpoints (boxes). a Dubins path are independent: a Dubins path 
an have high intri
a
y and low length (and vi
e versa). (a) LCL forbidden. (b) CCL forbidden. (
) Middle ar
 must be ≥ pi. (d) CCCC forbidden. Figure 2.2: Dubins' length redu
ing perturbations 
ontinuously deform a path from solid to dotted. By using the length redu
ing perturbations shown in Figure 2.2, Dubins keeps the set of 
anoni
al paths small. Theorem 2.1. [16℄ The stru
ture of a shortest bounded-
urvature path is a subsequen
e of CLC or CCC. If its stru
ture is CCC, the middle C-segment is longer than π. Boissonnat et al. prove the above theorem using 
ontrol theory [9℄. Although their proof is more 
on
ise, it la
ks the dire
t geometri
 reasoning of the earlier proofs. 9 2.2 Paths Amid Obsta
les We now 
onsider results about path planning in the presen
e of obsta
les. We begin our overview with two results that demonstrate that path planning is NP-hard in general 
ontexts. Then we survey three algorithms that are guaranteed to nd paths (when they exist) in general 
ontexts. These are the best results with whi
h to 
ompare our new results be
ause our new results also provide guarantees in general 
ontexts. We note that, unlike the algorithms developed in this thesis, these algorithms will nd paths of unbounded 
omplexity and length. However, also unlike the algorithms developed in this thesis, they also take super-polynomial time (in the worst 
ase, singly- or doubly-exponential in the size of the input). We then review results that nd paths in restri
ted domains in polynomially bounded time. In these restri
ted settings, the des
riptive 
omplexity of the desired path is polynomially bounded by the 
omplexity of the environment. Hen
e, our results generalise these results in that (a) they nd paths in more general 
ontexts and (b) when restri
ted to these domains, our results also nd paths in time that is polynomially bounded in terms of the environment 
omplexity (i.e. we 
an remove expli
it referen
e to k and λ from the bound on the run time), albeit with asymptoti
ally worse performan
e. Finally, we survey three approximation results that nd paths in general 
ontexts. To nd an approximation of a shortest path, it su
es to nd a path that is a slight distortion of a shortest path. In the 
ase of bounded-
urvature motion planning, the guarantees that a path will be found by the approximation results are weak. In 
hapter six, we 
ombine the idea behind these approximation results with new te
hniques found in this thesis to get an approximation algorithm with stronger guarantees. 2.2.1 Hardness Results The results reviewed in this se
tion ee
tively pla
e a lower bound on the time required to nd a shortest path: Canny and Reif show that nding a 3-dimensional Eu
lidean shortest path (3ESP) is NP-hard [13℄, and Reif and Wang argue that nding a 2- dimensional bounded-
urvature shortest path (2BSP) is NP-hard [23℄. Both redu
tions are 
on
eptually similar, so we outline the 
ommon 
ore. Both papers redu
e solving a 3-SAT instan
e with n variables and m 
lauses to nding the shortest path amid obsta
les. These hardness results not only suggest that it is impossible to e
iently nd an exa
t solution, but they bound how 
lose an e
ient algorithm 
an 
ome to the exa
t solution: the redu
tion of 3-SAT to 3ESP shows that it is NP-hard to nd a path that is at most 2−O(n) longer than the shortest path, where n is a measure of the problem size. We 
an split the set of feasible paths into homotopy 
lasses. A representative path of a homotopy 
lass is a shortest path in the homotopy 
lass. In the redu
tions to 3ESP and 2BSP, ea
h homotopy 
lass has exa
tly one representative path. Roughly speaking, ea
h representative path 
orresponds to a variable assignment in an instan
e of 3-SAT, whi
h we denote with a binary string of length n. The redu
tions rst 
reate 10 Θ(2n+m) homotopy 
lasses su
h that the dieren
e in the length between two dierent representative paths is at most 2−Ω(n 2) . Then for ea
h 
lause of the instan
e of 3-SAT, obsta
les are introdu
ed so that the length of representative paths that do not satisfy the 
lause be
ome at least 2−O(n) units longer than representative paths that do satisfy the 
lause. Hen
e, if there is a shortest path within 2−O(n) of a threshold, the instan
e of 3-SAT is satisable be
ause that path satises every 
lause. One 
riti
ism of the 2BSP 
onstru
tion is that it requires all representative paths to pass through holes of innitesimal width. Later in this survey, we introdu
e two measures of problem instan
e ill-
onditioning: pre
ision sensitivity and path robustness. The 2BSP 
onstru
tion is extremely pre
ision sensitive and the representative paths are non-robust. 2.2.2 General Domains The algorithms in this se
tion are mostly of theoreti
al interest be
ause they require exponential spa
e and (at least) exponential time. However, they provide a upper bound on the 
omplexity of various problems. Denoted ℜ(+,×), the rst order theory of the reals is the rst-order logi
 with real variables, inequalities, addition, and multipli
ation. Ea
h result in this se
tion 
reates a formula in ℜ (+,×) that satisable if and only if the underlying problem is solvable. Theorem 2.2. Satisability of a formula in ℜ(+,×) of length l, degree d, and with v variables 
an be tested in time (dl)2 O(v) [15℄ and spa
e (dl)O(v) [7℄. These redu
tions to ℜ (+,×) 
on
eptually work the same way. At the 
ore of ea
h result is an analysis that shows that the desired path be
omes a sequen
e of 
anoni
al subpaths when split by its 
onta
t with the environment. The redu
tions use real variables to represent potential environment 
onta
ts. They use 
lauses to (a) enfor
e the feasibility of a 
anoni
al subpath between 
onse
utive environment 
onta
ts and (b) guarantee the optimality of the entire path. Eu
lidean Shortest Path Reif and Storer des
ribe how to test if there exists a path Π that avoids three-dimensional polyhedral obsta
les su
h that the length of Π is less than some given algebrai
 number [24℄. The runtime of their algorithm is singly exponential in the problem size, whereas the previous best known result is doubly exponential. First they partition the polyhedral obsta
les into 
onvex regions, 
alled islands, whi
h introdu
es new ina

essible internal fa
es. They partition the obsta
les be
ause the shortest path along an island's surfa
e 
an be found in polynomial time [28℄. They want to minimise the size s of the de
omposition be
ause the number of real variables in the redu
tion to ℜ (+,×) is proportional s. However, it is NP-
omplete to nd the smallest su
h partition of a two-dimensional polygon [19℄. So Reif and Storer suggest the brute-for
e approa
h of enumerating all possible partitions in exponential time. 11 Figure 2.3: A shortest path (thi
k) 
omposed of dire
t paths (solid) and 
onta
t paths (dashed). A dire
t path is a line segment whose interior does not interse
t any obsta
les (see Figure 2.3). A 
onta
t path is a shortest path 
ontained on an island's a

essible fa
es. Finally, a fundamental path is a dire
t path followed by a 
onta
t path, either of whi
h may have length zero. Reif and Storer observe that (a) ea
h turning point on a shortest path o

urs on an obsta
le edge and (b) between 
onse
utive turning points, the shortest path either travels through free spa
e or along an obsta
le fa
e. These observations motivate their shortest path normal form: there exists a shortest path 
omposed of k fundamental paths. Determining if a dire
t path is obsta
le free or if there is a 
onta
t path of a 
ertain length 
an both be 
he
ked with a ℜ(+,×) formula of polynomially bounded size. By introdu
ing variables for ea
h of the k (possibly zero length) fundamental paths on the shortest path, Reif and Storer 
ombine these formulas to get a formula that is satisable if and only if there is a feasible path no longer than a given length. Kinodynami
 Qui
kest Traje
tory Canny et al. [12℄ redu
e nding the qui
kest kinodynami
 traje
tory in two dimensions under the L∞ norm to the satisability of ℜ(+,×). As des
ribed in Se
tion 2.1, they develop a 
losed form for the qui
kest traje
tory in the absen
e of obsta
les between two 
ongurations under the L∞ norm 
alled a 
anoni
al segment. Central to their approa
h is a theorem whi
h states that, independent of ve
tor norm, there is always a loop-free qui
kest traje
tory starting from and ending at rest. By loop, they mean a traje
tory that begins and ends at the same position, regardless of the parti
ular starting and ending velo
ities. To prove this theorem, they rst show how to 
reate a new traje
tory that tra
es the path of a given traje
tory. This new traje
tory starts at rest and greedily a

elerates whenever possible until it 
at
hes the original traje
tory or rea
hes the end of the path. At every point on the path, the magnitude of the velo
ity of the tra
ing traje
tory is less than the magnitude of 12 the velo
ity of the original traje
tory be
ause the new traje
tory follows the original traje
tory if the traje
tories ever 
oin
ide. This allows the authors to bound the time dieren
e between the two traje
tories at any point p on the path in terms of the velo
ity dieren
e at p and maximum a

eleration bound. They then use this bound to show that spli
ing out the loop by 
oming to a 
omplete stop, instantaneously turning, and starting from rest is no slower than following the loop. By using a 
ontinuous deformation argument, Canny et al. show that a qui
kest traje
tory 
an be viewed as a sequen
e of 
anoni
al segments. They also give a simple argument bounding the number of 
anoni
al segments: if a traje
tory tou
hes a wall twi
e, then we 
an spli
e out the middle and greedily follow the wall with no penalty; if a traje
tory tou
hes a 
orner twi
e, then we have a loop that 
an be eliminated. This means that the total number of 
anoni
al segments is at most linear in the 
omplexity of the environment. The 
losed form for 
anoni
al paths and small number of 
anoni
al segments on a qui
kest traje
tory give us a redu
tion to the rst order theory of the reals. Bounded Curvature Path Feasibility Fortune and Wilfong determine if a feasible bounded-
urvature path exists in the pres- en
e of polygonal obsta
les with a redu
tion to ℜ(+,×) [17℄. Unlike the other redu
tions in this se
tion, the variables in the redu
tion do not 
orrespond to one parti
ular path, but a 
ontinuous range of paths. This representation of paths is so 
ompa
t that it not 
lear that one parti
ular path from the range 
an be extra
ted e
iently. Fortune and Wilfong use path normalisation to redu
e the problem of nding a feasible path to nding regions of the environment boundary that 
an be rea
hed. They rst show that if there is a feasible bounded 
urvature path amid obsta
les from a start 
onguration to a terminal 
onguration, there is a feasible Dubins path amid obsta
les from the same start 
onguration to the same terminal 
onguration. Then, they for
e every C-segment to tou
h an obsta
le. To do this, Fortune and Wilfong assume without loss of generality that the obsta
le-free spa
e is bounded : this 
an be a
hieved by surrounding the obsta
les with a large bounding box; by making the box large enough, the original problem admits a feasible path if and only if the new problem admits a feasible path. We des
ribe Fortune and Wilfong's path normalisation in greater detail in Chapter 3, where we extend their normalisation. Fortune and Wilfong dene a jump as a Dubins path whose stru
ture is a subse- quen
e of CLC. By splitting a normalised Dubins path where C-segments tou
h the environment, the path is de
omposed into a sequen
e of jumps. In this sense, a jump repla
es the notion of a 
anoni
al subpath in the previous results. The dieren
e be- tween the denition of a jump and a 
anoni
al subpath is slight: jumps 
annot have stru
ture CCC whereas 
anoni
al subpaths 
an. Fortune and Wilfong use jumps in- stead of 
anoni
al subpaths to redu
e the number of 
ases that they 
onsider in their analysis. In the next 
hapter, we use a more restri
tive notion of a jump to further de
rease the number of 
ases that we 
onsider in our analysis. 13 A feature refers to some parti
ular 
orner or wall of the environment. Ea
h 
onta
t that a feasible path has with the environment only has one degree of freedom: where a path tou
hes a wall, the point of 
onta
t 
an lie anywhere on the wall (a 
ontinuous range), but the orientation of 
onta
t must be parallel to the wall; where a path tou
hes a 
orner, the point of 
onta
t is xed, but the orientation of 
onta
t 
an lie anywhere in a 
ontinuous range. Hen
e, we 
an 
ompa
tly represent ranges of rea
hable 
onta
t with an interval: at walls, we use an interval of the wall augmented with one of two possible dire
tions; at 
orners, we use an interval of orientations. W θ C (a) Destination 
ongurations point to the left. W θ C (b) Destination 
ongurations point to the right. Figure 2.4: A rea
hable interval (dashed) on wall W from an start 
onguration θ (dotted) from a 
orner C. Fortune and Wilfong rst des
ribe all of the 
ongurations at a feature that 
an be rea
hed by a jump from a single 
onguration at another feature. In Figure 2.4, for example, a single 
onguration θ at 
orner C 
an rea
h two intervals of 
ongurations at wallW using a single jump. This denes the propagation by one jump of a 
onguration to a set of rea
hable intervals. Building on this, Fortune and Wilfong des
ribe how to propagate an interval of rea
hable 
ongurations to a family of rea
hable intervals. Let Ij be the family of rea
hable intervals that 
an be rea
hed from the start 
onguration using at most j jumps. Then Ij+1 
an be derived from Ij using interval propagation. Fortune and Wilfong's redu
tion to R (+,×) nds the smallest I∗ that 
ontains the start 
onguration θ and is 
losed with respe
t to interval propagation. This 
losure I∗ 
orresponds to the xed-point of Ij . Note that there is no guaranteed rate of 
onvergen
e to the xed-point I∗. That is, every 
onguration in I∗ is rea
hable by a path of nite intri
a
y, but this intri
a
y may be arbitrarily large. Related to this observation, the rea
hable intervals of Ij are all 
losed but the intervals of I∗ may be open be
ause ea
h endpoint of an interval in I∗ is a limit, whi
h may or may not be rea
hed. To keep the representation of I∗ su

in
t, Fortune and Wilfong merge rea
hable intervals in I∗ whenever they interse
t. A 
ore result of their paper is that I∗ 
ontains a polynomially bounded number of intervals after merging. Fortune and Wilfong 
on
lude with a redu
tion to ℜ(+,×) that denes I∗: they use real variables to represent intervals of I∗, various formulas to 
lose I∗ with respe
t to jumps, and other formulas to spe
ify that I∗ is the smallest su
h set with an interval 
ontaining the given start 
onguration. 14 2.2.3 Restri
ted Domains The study of bounded-
urvature paths in restri
ted domains started as a way of solving problems of real-world interest [29℄. In the fa
e of Reif and Wang's NP-hardness result, restri
ted domains are used to regain tra
tability and to understand what makes this motion planning problem di
ult. Moderate Obsta
les Agarwal et al. [2℄ give an algorithm for nding the shortest path amid moderate ob- sta
les, where an obsta
le is moderate if it is simple, 
onvex, and our point robot 
an tra
e its boundary (see Figure 2.5). This is a very restri
ted problem: if there were no orientation asso
iated with the start and terminal 
onguration, then this problem is equivalent to the Eu
lidean shortest path problem in two dimensions. initial goal Figure 2.5: Some moderate obsta
les. The majority of this paper develops a strong 
hara
terisation of shortest paths amid moderate obsta
les, from whi
h a straightforward algorithm follows. First a few denitions: an O-segment is a 
ontiguous pie
e of an obsta
le boundary; a terminal 
ir
le/C-segment is tangent to either the start or the terminal 
onguration; a an- 
hored 
ir
le/C-segment is tangent to two obje
ts, ea
h of whi
h is either an obsta
le or terminal 
ir
le; and a oating 
ir
le/C-segment tou
hes only one obsta
le or terminal 
ir
le. Agarwal et al. show that on every shortest path amid moderate obsta
les (see Figure 2.6) 1. if there are three C-segments in a row, then either the rst or last C-segment is terminal; 2. all C-segments are either an
hored or oating; 3. there are at most two oating C-segments  when there are exa
tly two, they o

ur 
onse
utively; 4. and the 
entre of the rst (respe
tively last) oating C-segment is at most two units from the start (respe
tively terminal) 
onguration. The approximation algorithm of Agarwal et al. treats an
hored 
ir
les and oating 
ir
les as pseudo-obsta
les: like obsta
les, they 
an be travelled to and along, but unlike 15 initial goal Figure 2.6: A oating pair of C-segments. obsta
les, they 
an be passed through. While there are only O(n) an
hored 
ir
les, where n is the obsta
le 
omplexity, there are innitely many possible oating 
ir
les. To limit the number of oating pairs 
onsidered, Agarwal et al. sample the spa
e of possible oating pairs uniformly to get O (ε−1) relevant pairs. The upper bound on the number of relevant pairs is independent of the obsta
le geometry be
ause the pair 
entres must be 
lose to the start and terminal 
ongurations and the obsta
les are moderate. Agarwal et al. then 
onstru
t a weighted visibility graph, where the nodes are the 
ongurations (and their dire
tional reversals) shared between obsta
les, an
hored 
ir- 
les, relevant pairs, and the tangents between them. They add a weighted edge between two nodes if some O-, C-, or L-segment joins them su
h that the segment does not pass through an obsta
le or another node. The weight of the edge is the shortest path found between nodes. They show that the visibility graph 
an be 
onstru
ted and sear
hed in O ( (n+ ε−1)2 log (n+ ε−1) ) time. Boissonnat and Lazard [10℄ rene this result to get an exa
t O(n2 logn) time algo- rithm, where n is the 
omplexity of the moderate obsta
les. The essen
e of their paper is a more rened 
hara
terisation of shortest paths, whi
h redu
es the number of pla
e- ments of oating pairs. Spe
i
ally, they show that a oating pair on a shortest path is part of subpath with stru
ture XLCCLX ′, where X ,X ′ ∈ {O,CA} and CA is an an- 
hored 
ir
le. As ea
h oating C-segment must tou
h an obsta
le, there are only O(n4) 
ombinatorial arrangements for a oating C-segment. Agarwal et al. noted that oating C-segments must o

ur 
lose to the start and terminal 
ongurations, whi
h further redu
es the number of 
ombinatorial arrangements to O(c4), where c is some 
onstant upper bounding the number of obsta
les 
lose to the start and terminal 
ongurations. Boissonnat and Lazard also show that there are only a xed number of pla
ements of oating pairs for ea
h 
ombinatorial arrangement by analysing the equilibria of a me- 
hani
al system modelling the shortest path through the arrangement. These equilibria 
orrespond to high, but xed, degree polynomials. This gives an O(n2 logn) time exa
t algorithm be
ause the time taken to nd the roots of these polynomials is a

ounted for by the hidden 
onstants in the asymptoti
 notation. 16 Convex En
losure Agarwal et al. [1℄ analyse the stru
ture of shortest bounded-
urvature paths inside 
onvex polygons. This leads to a polynomial time algorithm. Some of the results from their study of moderate obsta
les hold in this domain as well: spe
i
ally (a) no non-terminal C-segment has length greater than π, (b) every non-terminal C-segment is tangent to the boundary or terminal 
ir
le in at least one point, and (
) no subpath that ex
ludes the rst and last C-segment has type CCC. Agarwal et al. also introdu
e the notion of a po
ket that on
e entered 
annot be left and vi
e versa, whi
h substantially redu
es the spa
e of possible paths. One of the more interesting results in this domain is that an optimal path has at most one non-terminal CC subpath, and any non-terminal C-segment that pre
edes (respe
tively follows) su
h a C1C2 subpath is oriented the same way as C1 (respe
tively C2). Hen
e, any non-terminal CC subpath denes a turning point. A rigorous 
hara
terisation of the remaining types of paths shows that every optimal path is a subsequen
e of CICSCCSCCG where CI ,CG are terminal C- segments. Agarwal et al. a
hieve an O(n logn) algorithm with an analysis of C-segment 
onta
t, where n is the number of 
orners of the 
onvex polygon. Ahn et al. 
hara
terise the positions inside a 
onvex polygon that 
an be rea
hed by bounded-
urvature paths [4℄. Spe
i
ally, their analysis ignores the orientation and just fo
uses on lo
ation. By s
aling the polygon, they assume that the 
urvature bound is one. Their results rely on two key lemmas: the Pestov-Ionin Lemma that gives a su
ient 
ondition for a 
losed bounded-
urvature 
ir
uit to 
ontain a unit radius dis
, and the Po
ket Lemma proved by Agarwal et al. [1℄. Ahn et al. start with an analysis of the region that is rea
hed from a 
onguration on the polygon boundary. Then for a given start 
onguration inside the polygon, they 
onsider four 
anoni
al traversals to ea
h polygon edge, whi
h redu
es the rea
hable area to regions just 
overed. The entire rea
hable region is found by iterating over all polygon edges and adding regions that are dire
tly a

essible from the start 
onguration (i.e. rea
hable via one C- and one L-segment). They 
on
lude by showing that the rea
hable region has O(n) 
omplexity, where n is the number of 
orners of the polygon. Narrow Corridors Bereg and Kirkpatri
k look for bounded-
urvature paths in a domain akin to non- bran
hing roadways [8℄. Again, the environment is s
aled so that the 
urvature bound is one. If Π is a feasible path, the 
orridor about Π is the region swept out as the 
entre of a dis
 of xed diameter w tra
es Π. A 
orridor C is redu
ible if some other feasible path Π′ has an asso
iated 
orridor C ′ 
ontained in C (see Figure 2.7). In a redu
ed 
orridor, the path followed by the tra
ing dis
 has bounded-
urvature (its minimum radius of 
urvature is w/2). Bereg and Kirkpatri
k try to nd paths from one end of the 
orridor to the other. They restri
t their attention to irredu
ible 
orridors with width less than two be
ause, if the width is greater or equal to two, the path tra
ed by the dis
 is a bounded-
urvature traversal of the 
orridor. The 
ore result of Bereg and Kirkpatri
k is a width threshold τ su
h that every 17 Figure 2.7: A 
orridor (left) and its redu
ed 
orridor (right), both of whi
h are tra
ed by a dis
 following a path. 1 1 1 Figure 2.8: A robot with a turning radius of one 
annot traverse this 
orridor. 
orridor with w > τ 
an be traversed and for every w < τ there are 
orridors of width w that 
annot be traversed (see Figure 2.8). The proof that 
orridors with w > τ admit a traversal is provided by a greedy algorithm. 2.2.4 Approximation Algorithms The hardness results presented earlier motivate the sear
h for e
ient approximation algorithms. All of the (1 + ε)-approximation algorithms des
ribed below use a weighted visibility graph: the nodes 
orrespond to potential path 
onta
t with the environment; the range of possible path 
onta
t is sampled with a granularity that is monotoni
 in ε; edges between nodes 
orrespond to the shortest 
anoni
al subpath between 
onta
ts; the shortest path in the visibility graph 
orresponds to a path that is at most (1 + ε) times longer than the desired optimal path. Eu
lidean Shortest Path The rst approximation algorithm that we dis
uss nds an approximation to the un- 
onstrained shortest path in three dimensions amid arbitrary polyhedral obsta
les. In this setting, the edges of polyhedral obsta
les play an important role. We use refer to an edge of an obsta
le as a ridge to distinguish it from an edge of a visibility graph. Eu
lidean shortest paths bend at ridges and only visit ea
h a ridge at most on
e. 18 Papadimitriou partitions ea
h ridge into fragments, where ea
h fragment represents a potential path 
onta
t with a ridge [21℄. His subdivision is highly non-uniform in the sense that fragments of the same ridge will have quite dierent lengths. Ea
h node in his visibility graph 
orresponds to a fragment, and an edge between nodes 
orresponds to the shortest, feasible, straight-line path between two fragments. A path P in the visibility graph 
orresponds to a Eu
lidean path Π: ea
h edge in P 
orresponds to a hop between fragments; to 
onstru
t Π, we glue these hops together  we 
an transition between hops that o

ur 
onse
utively on P by following the fragment that they both tou
h. By keeping the size of ea
h fragment relatively small, the length of Π is dominated by its hops between fragments rather than its transitions between 
onse
utive hops. In this 
ase, Π is a good approximation of the Eu
lidean shortest path. Papadimitriou partitions a ridge into fragments as follows. He rst identies the point p on the ridge 
losest to the start position. The distan
e d from the start position to p lower bounds the length of any path from the start position to the ridge. The smallest fragment f of the ridge 
ontains p. The length of f is a fun
tion of d so that the error in approximation due to gluing hops together via f is dominated by the length of the path rea
hing f . Spe
i
ally, the size of this fragment is proportional to ε and inversely proportional d and the total number of ridges n (the maximum number of fragments visited by a shortest path). The size of a ridge fragment in
reases geomet- ri
ally the further it gets from the smallest fragment: Papadimitriou assumes that the 
oordinates of ea
h ridge endpoint are spe
ied in xed-point arithmeti
 representation with at most m digits; this limited pre
ision implies that the length of a ridge is at most 2O(m) and the distan
e from the start position to a ridge is at least 2−O(m); hen
e, ea
h ridge subdivides into a polynomially bounded number of fragments. Rened Analysis Papadimitriou 
omputes within an algebrai
 framework, but his analysis assumes a bit model representation of input (xed-point). Choi et al. 
arry out a detailed analysis that substitutes oating point arithmeti
 of su
ient pre
ision for real arithmeti
 [14℄. In [26℄, Choi et al. introdu
e a bit model parameter δ−1 that measures problem instan
e di
ulty. This measure is exponential for instan
es generated by the redu
tion that proves that 3ESP is NP-hard. Choi et al. distinguish between the 
ombinatorial and numeri
al aspe
ts of 3ESP; they say that two paths in 3ESP are 
ombinatorially distin
t if they 
onta
t a dierent sequen
e of obsta
le edges. Let d1 be the length of shortest path and d2 be the length of the shortest path that is 
ombinatorially distin
t from the path 
orresponding to d1. They dene the pre
ision sensitivity of the problem as δ ≡ (d2−d1)/d1. In the bit model of 
omputation, the runtime of the approximation algorithm is polynomially bounded in n, m, ε−1, and δ−1. 19 Kinodynami
 Shortest Path The kinodynami
 approximation algorithms do not nd an approximation to the short- est path. Rather they nd a (1 + ε)-approximation to the shortest δ-safe path: a path is δ-safe if every point on the path is at least δ units away from every obsta
le. Spe
if- i
ally, these algorithms are not true shortest path approximation algorithms be
ause, in general, the shortest δ-safe 
an be arbitrarily longer than the shortest path. The restri
tion to δ-safe paths is exploited algorithmi
ally. Intuitively, there is a range of feasible paths surrounding a shortest δ-safe path Π. In order to approximate Π, it su
es to sear
h for a feasible path Π′ in the obsta
le free region surrounding Π. The safety of Π allows us to restri
t our attention to a Π′ that is 
omposed of a sequen
e of 
anoni
al subpaths. A drawba
k of this approa
h is that Π′ may not be δ-safe, even though Π is δ-safe. One 
hallenge in approximating the shortest δ-safe path is 
hoosing an appropriate set of 
ongurations to use as nodes in the visibility graph. In parti
ular, it is insu
ient to sample the surfa
e of the obsta
les be
ause a δ-safe path never tou
hes the obsta
le boundary. Instead, Reif and Wang use non-uniform grid de
omposition of free spa
e [25℄. This leads to the asymptoti
ally state-of-the-art polynomial time algorithm for approximating the kinodynami
 shortest path. Their free spa
e box-de
omposition method is very similar to an o
t-tree de
omposition of free spa
e: they start with a d-dimensional 
ube that 
ontains all of the obsta
les; if a 
ube 
ontains part of an obsta
le, then they re
ursively split it into 2d 
ubes, ea
h with half the side length of the original; they never de
ompose a 
ube with side length less than cδ, where c is a 
onstant; and if a 
ube shares a fa
e with a 
ube that has a side length more than twi
e as large, then they split the larger 
ube. The last rule guarantees ne sample granularity near obsta
les. Reif and Wang uniformly pla
e O(1/εd−1) sample position points along ea
h box fa
e surrounded by empty boxes, and they uniformly sample all possible velo
ity ve
tors with O(1/εd) velo
ities. The nodes of the visibility graph are the Cartesian produ
t of sample positions and sample velo
ities. Edges are added between nodes on a fa
e and nodes on the fa
es of an extended box 
ontaining the fa
e, whi
h is essentially the union of the boxes 
ontaining that fa
e. The length of an edge 
orresponds to the length of a 
anoni
al path between the 
ongurations joined by the edge. In general, 
anoni
al paths 
annot be 
omputed dire
tly be
ause there is no simple 
losed form (ex
ept for the L∞ norm). So, an approximation to the 
anoni
al path is substituted. The set of approximate 
anoni
al paths is independent of the parti
ular obsta
le geometry and 
an be pre
omputed. The side length ratio limit of the box-de
omposition redu
es the number of approximate 
anoni
al paths that are pre
omputed. Bounded-Curvature Shortest Path The length redu
ing deformations used by Dubins to 
hara
terise bounded-
urvature shortest paths in the absen
e of obsta
les are 
ontinuous. Hen
e, his results have immediate 
onsequen
es amid polygonal obsta
les. Ja
obs and Canny expli
itly state 20 this in their work on approximating shortest bounded-
urvature paths [18℄. Theorem 2.3. Let Π be a shortest bounded-
urvature path in the presen
e of polygonal obsta
les. The 
ongurations where Π just tou
hes the environment partition Π into 
ollision free subpaths. Ea
h of these subpaths has the stru
ture of a shortest bounded- 
urvature path in the absen
e of obsta
les (see Theorem 2.1). We say that a path Π is JC-normal if splitting Π where it just tou
hes the envi- ronment results in a sequen
e of subpaths that have the form of a shortest bounded- 
urvature path in the absen
e of obsta
les. Rather than nding an approximation to the shortest path, the bounded-
urvature approximation algorithms nd a (1 + ε) approximation to the shortest ε-robust path: we say that a JC-normal path Π is ε-robust if ea
h point where Π just tou
hes the environment 
onta
t 
an be perturbed (simultaneously and independently) by ε without 
hanging the feasibility or stru
ture of Π. By perturb we mean that if Π just tou
hes a wall, we 
an slide that 
onta
t by ε along the wall (see Figure 2.9(a)), and if Π just tou
hes a 
orner, we 
an pivot that 
onta
t by ε radians at the 
orner (see Figure 2.9(b)). This restri
tion to ε-robust paths allows us to restri
t our node set: if we sample the spa
e of potential path 
onta
ts with a granularity proportional to ε (dots and arrows in Figure 2.9), an ε-robust path 
an be deformed so that every environment 
onta
t o

urs at a sample point, in whi
h 
ase, a 
anoni
al subpath joins 
onse
utive 
onta
t points. We make our granularity proportional to ε to ensure that the resulting path is at most (1 + ε) times longer than the original path. This argument is explained in greater detail in Chapter 6, where we des
ribe a new result that extends the previous approximation algorithms. ε (a) The path's wall 
onta
t 
annot be perturbed by ε. ε (b) The path's 
orner 
onta
t 
annot be per- turbed by ε. Figure 2.9: Environment 
onta
ts that not ε robust. To 
reate the nodes of their visibility graph, Ja
obs and Canny [18℄ sample the potential path 
onta
ts at a feature with granularity proportional to ε (see Figure 2.9). They then give two methods of 
onstru
ting the weighted edges: one guarantees that the 
orresponding path is robust and the other does not. Let n be the number of 
orners and w be the total length of the walls. The total runtime of the graph 
onstru
tion and 21 sear
h for the robust approa
h is O ( (n+ w)2 ε−4 + n4 logn ) whereas the total runtime for the non-robust approa
h is O ( (n+ w)2 ε−4 + n2 (n+ w) ε−2 logn ) . Wang and Agarwal revise the algorithm of Ja
obs and Canny to get a tighter asymp- toti
 bound [3℄. Their major 
ontribution is eliminating the asymptoti
 dependen
e on w. We say that a path 
onta
t c is witnessed by a point p if cp is a unobstru
ted line segment of length no more than 15. Wang and Agarwal prove that every path 
onta
t with a wall on a shortest robust path is witnessed by a 
orner. Only O(n) length of wall is witnessed by 
orners, where n is the number of 
orners. Wang and Agarwal also use a dierent method to generate the edges of the weighted visibility graph. This faster method for generating weighted visibility edges redu
es the runtime 
omplexity to O(n2ε−4 log n). 22 Chapter 3 Normal Forms Path normalisation plays a 
riti
al role in our design and analysis of path-planning algorithms. Spe
i
ally, the stru
ture imposed on paths by normalisation dire
ts our approa
h to nding paths, our proof that the approa
h is 
orre
t, and our analysis of the e
ien
y of the approa
h. In this 
hapter, we des
ribe how to normalise paths so that every normal path has a dis
rete des
ription: this allows us to perform a 
ombina- torial sear
h for a path, to make this sear
h exhaustive, and to bound the run time of the sear
h by bounding the size of its sear
h spa
e. Considering the vital role that nor- malisation plays in this thesis, it is not surprising that all previous bounded-
urvature path-nding results also rely on normalisation: the shortest-path results impli
itly nor- malise paths by looking for optimal paths (see Se
tion 2.1) and the feasibility result expli
itly des
ribes how to normalise paths (see Se
tion 2.2.2). To start this 
hapter, we des
ribe a minor modi
ation to the normalisation of Fortune and Wilfong [17℄. The spa
e of all su
h FW-normal paths is 
ontinuous. After that, we des
ribe our major extension to this normalisation. The spa
e of all su
h BK-normal paths is 
ountable and, hen
e, systemati
ally sear
hable. The way that we get a BK-normal path from a FW-normal path 
an be illustrated with a simple analogy. A FW-normal path is like a plumber's snake that has been threaded through a sequen
e of pipes: every bend is 
onstrained by a pipe, but the bends retain some freedom, whi
h allow the snake to be twisted. To make su
h a path BK-normal, we an
hor the end of the plumber's snake and twist the snake until its elasti
ity is stret
hed to its breaking point. The 
ombination of internal 
onstraints (elasti
ity) and external 
onstraints (pipes) removes all freedom from the plumber's snake. This total la
k of freedom allows us to des
ribe the snake in terms its 
onstraints (where it tou
hes the pipes and how it bends). Whereas this des
ription of the snake has 
ontinuous elements, our des
ription of an a
tual BK-normal path is dis
rete be
ause the a
tual path 
onstraints have a dis
rete des
ription. 23 3.1 Fortune and Wilfong Normal Form We exploit path normalisation to simplify our algorithm design and improve our algo- rithm's e
ien
y. We want to 
hoose our normal form so that the spa
e of normal paths is small and normal paths are easy to nd and des
ribe. These two goals 
ompete in the sense that a
hieving one 
omes at the expense of the other: as we make our normal form more restri
tive, the more intri
ate the simplest desired normal path be
omes, but the smaller the spa
e of all normal paths be
omes. We make this 
ompromise expli
it by quantifying how the intri
a
y of the desired path in
reases as we limit our attention to more restri
tive normal forms (and smaller path spa
es). Earlier, we surveyed prior bounded-
urvature path normalisations (see Se
tions 2.1 and 2.2.2). Re
all that a Dubins path is a dierentiable path made of C-segments (ar
s of unit-radius 
ir
les) and L-segments (straight-line segments). Fortune and Wilfong des
ribe how to turn an arbitrary feasible bounded-
urvature path into a Dubins path in the presen
e of obsta
les [17℄. Hen
e, we 
an restri
t our path sear
h to Dubins paths. Also re
all that we dene the intri
a
y of a Dubins path as the number of its (non- zero) segments. We 
hoose this measure be
ause the length of a natural des
ription of a Dubins path is proportional to the number of its segments. In this sense, the intri
a
y of the simplest desired Dubins path is a lower bound on the run time of any algorithm that returns an expli
it des
ription of a feasible Dubins path. After turning a given bounded-
urvature path into a Dubins path, Fortune and Wilfong deform the result to 
onstrain its turns. Intuitively, these deformations either eliminate a path C-segment (see Figure 3.1(b)) or push it into 
onta
t with the envi- ronment (see Figure 3.1(
)). On
e this phase nishes, ea
h internal C-segment tou
hes some obsta
le (there may be a C-segment at the start and end that do not tou
h an obsta
le). This phase 
an be applied to any Dubins path. Fortune and Wilfong argue the entire pro
ess in
reases the path intri
a
y by a fa
tor of at most n (the number of obsta
le 
orners). (a) Initial Dubins path. (b) Pop out C-segments. (
) Pull in C-segments. (d) Push out C-segments. Figure 3.1: Deformations used in FW normalisation. 24 We add one more phase to Fortune and Wilfong's normalisation: if some π-length subar
 does not tou
h an obsta
le, we slide a π-length subar
 (not ne
essarily the same subar
, but a related one) like part of a trombone until it tou
hes an obsta
le (see Figure 3.1(d)). Like Fortune and Wilfong, we assume without loss of generality that the obsta
le-free spa
e is bounded. Hen
e, the sliding subar
 eventually tou
hes an obsta
le. By 
areful 
hoi
e of what fragment to slide, we guarantee that the re- maining, unperturbed portions of the original C-segment also tou
h an obsta
le. Ea
h time we slide a subar
, we break one C-segment into at most ve path segments (see Figure 3.1(d)). Hen
e, we at most quintuple the intri
a
y of the path in the worst 
ase. Theorem 3.1. [17℄ Suppose that there exists a feasible Dubins normal path of intri
a
y k from start 
onguration αs to terminal 
onguration αt. Then there exists a feasible Dubins normal path of intri
a
y at most 5nk from αs to αt su
h that 1. every internal C-segment tou
hes an obsta
le and 2. every subar
 of length π tou
hes an obsta
le. We refer to any Dubins path with the above properties as FW-normal. Like Fortune and Wilfong, we refer to a FW-normal path with stru
ture CLC (ea
h segment 
an be zero length) as a jump. Our denition of jump diers from Fortune and Wilfong's denition of jump in one respe
t: we now require that every C-segment on a jump has length at most π. α ωβ (a) Path is a jump from α to ω or a jump from α to β followed by a jump from β to ω. p q (b) The point p just tou
hes an obsta
le but q does not. Figure 3.2: Representing a FW-normal path as a sequen
e of jumps. Jumps are important be
ause we represent FW-normal paths as a sequen
e of jumps. For example, the FW-normal path in Figure 3.2(a) is a jump from α to β followed by a jump from β to ω. The following lemma states that any FW-normal path 
an be represented as a sequen
e of jumps. In general, there are several ways to represent a FW-normal path as a sequen
e of jumps: in Figure 3.2(a), the path from α to ω is also a single jump. We now remove ambiguity in how we represent a path by jumps. We say that a point p of a path Π just tou
hes an obsta
le, if p tou
hes an obsta
le and some point on Π arbitrarily 
lose to p does not tou
h an obsta
le. For example, the point p in Figure 3.2(b) just tou
hes an obsta
le, but the point q does not just tou
h an obsta
le. We 
an obtain a unique representation of Π by splitting it at all of the points where Π just tou
hes the environment. This results in a nite sequen
e be
ause ea
h segment of Π just tou
hes ea
h feature at most twi
e. 25 We say that a jump is 
anoni
al if no point in its interior just tou
hes an obsta
le. Referring ba
k to Figure 3.2(a), the jump from α to ω is non-
anoni
al but both jumps from α to β and from β to ω are 
anoni
al. We say that a sequen
e of jumps 〈Ji〉 is a 
anoni
al representation of a path Π if (a) ea
h jump Jj is 
anoni
al, (b) Jj and Jj+1 meet at a point where Π just tou
hes the environment, and (
) Π is the 
on
atenation of the jumps in 〈Ji〉. The next lemma bounds the size of a path's 
anoni
al representation in terms of the intri
a
y of the path and the 
omplexity of the environment. Lemma 3.2. Suppose that there exists a Dubins path from start 
onguration αs to terminal 
onguration αt with intri
a
y k. Then there exists a FW-normal path from αs to αt whose 
anoni
al representation 
onsists of O(nk + n 2) jumps. Proof. By Theorem 3.1, let Π be a FW-normal path from αs to αt with O(nk) intri
a
y. To a
hieve the desired bounds on the size of its 
anoni
al representation, we rst remove some redundan
y from Π. Let 〈Ji〉 be the 
anoni
al representation of Π. If Jj = Jl, for j < l, the subpath 
orresponding to 〈Jj , . . . , Jl−1〉 forms a loop (it begins and ends at the same 
onguration), in whi
h 
ase we remove the subpath from Π and the subsequen
e from 〈Ji〉. Let 〈J ′i〉 be the result of removing all su
h loops. Let Π′ be the 
on
atenation of jumps in 〈J ′i〉. Clearly, Π′ is FW-normal and 〈J ′i〉 is its 
anoni
al representation. To prove this lemma, it su
es to show that the length of 〈J ′i〉 is O(nk + n2). We rst bound the number of jumps of 〈J ′i〉 that 
onsist of more than one non-zero segment: Π′ has intri
a
y O(nk) be
ause it is a subpath of Π; hen
e, Π′ has O(nk) transitions from one non-zero length segment to another; therefore, there are O(nk) jumps of 〈J ′i〉 that 
onsist of more than one non-zero segment be
ause ea
h su
h jump 
ontains at least one su
h transition of Π′. Now we bound the number of jumps of 〈J ′i〉 that 
onsist of exa
tly one non-zero segment: there are O(1) 
anoni
al jumps from one feature to another feature that 
onsist of exa
tly one segment; hen
e, there are O(n2) unique 
anoni
al jumps that 
onsist of exa
tly one segment; therefore, there are O(n2) jumps of 〈J ′i〉 that 
onsist of exa
tly one segment be
ause J ′j 6= J ′l , for j < l. (a) There is at most one L- segment from one oriented 
ir- 
le to another. θ (b) There are two oriented unit-radius 
ir
les tangent to θ. θ φ (
) There are at most four CLC-stru
ture paths from θ to φ. Figure 3.3: Observations leading to our jump representation. Our goal is to develop a normal form where every normal path has a dis
rete de- s
ription. We just illustrated that a path 
an be represented as a sequen
e of jumps. 26 If every jump in su
h a sequen
e has a dis
rete des
ription, the path has a dis
rete de- s
ription. Before normalising a path to give its jumps a dis
rete des
ription, we argue that every jump has a su

in
t des
ription: its rst 
onguration, its last 
ongura- tion, and a detailed des
ription of its stru
ture. Re
all that the stru
ture of a jump is CLC, where any segment 
an have zero length. We view the L-segment of a jump as a transition from the oriented 
ir
le underlying the rst C-segment to the oriented 
ir
le underlying the se
ond C-segment (see Figure 3.3(a)). This transition is uniquely dened by the oriented 
ir
les be
ause there is at most one L-segment from one ori- ented 
ir
le to another. Note that there are two oriented unit-radius 
ir
les tangent to any 
onguration (see Figure 3.3(b)). Hen
e, a jump from a 
onguration θ to a 
onguration φ is a transition from one of two 
ir
les tangent to θ to one of two 
ir
les tangent to φ (see Figure 3.3(
)). Thus, there are at most four possible jumps from θ to φ. To 
ompletely spe
ify a jump, we distinguish between these four possibilities using a more rened notion of path stru
ture that we 
all the signed stru
ture of a path: we augment ea
h C in the stru
ture with a supers
ript indi
ating the orientation of its 
orresponding C-segment  `+' for 
lo
kwise and `-' for 
ounter
lo
kwise. The above observations imply that a jump is 
ompletely determined by its rst 
onguration, its last 
onguration, and its signed stru
ture (one of C+LC+, C+LC−, C−LC+, and C−LC−). In the next 
orollary, a 
onta
t 
onguration of a path Π refers to either the rst 
onguration on Π, the last 
onguration on Π, or a 
onguration where Π just tou
hes the environment. Corollary 3.3. Suppose that there is a Dubins path from 
onguration αs to 
ongu- ration αt with intri
a
y k. Then there exists a FW-normal path Π from αs to αt that 
an be represented as sequen
e of 
onta
t 
ongurations 〈θi〉 and a sequen
e of signed stru
tures 〈Γi〉 su
h that 1. the ith jump in the 
anoni
al representation of Π is the jump from θi to θi+1 with signed stru
ture Γi, 2. the lengths of 〈θi〉 and 〈Γi〉 are O(nk + n2). 3.2 Combinatorial Augmentation We now dene new normal form where ea
h normal path has a dis
rete des
ription. This dis
rete des
ription is an extension of the path representation stated in the pre- 
eding 
orollary. The potentially non-dis
rete elements in the path representation of Corollary 3.3 are the 
onta
t 
ongurations. In this se
tion, we des
ribe how to deform a path in a way that ea
h 
onta
t 
onguration has a dis
rete des
ription. In general, a 
onguration has three degrees of freedom be
ause it 
an be translated horizontally, translated verti
ally, and rotated. However, the 
onta
t 
ongurations of a FW-normal path are restri
ted in the following sense: if a 
onta
t 
onguration o

urs at a 
orner, its position is xed by the 
orner but its orientation lies in a 
ontinuous 27 range; if a 
onta
t 
onguration o

urs at a wall, its position belongs to a 
ontinuous range (the wall) but its orientation must be parallel to the wall. Intuitively, we dis
retise our des
ription of a FW-normal path by pushing ea
h degree of freedom to its limit. For example, if a 
onta
t 
onguration o

urs at a 
orner, we may pivot it around the 
orner (see Figure 3.4(a)); if a 
onta
t 
onguration o

urs at a wall, we may slide it along the wall (see Figure 3.4(b)). Ea
h su
h deformation arti
ially 
onstrains the freedom of the perturbed 
onta
t 
onguration: it maintains 
onta
t with a parti
ular feature, even though we 
ould (in many situations) translate the 
onguration away from its 
onta
t without violating feasibility. (a) Range of possible 
orner 
onta
ts. (b) Range of possible wall 
onta
ts. Figure 3.4: By requiring a 
onta
t 
onguration to tou
h some feature, it has just one degree of freedom. We 
all perturbing a 
onta
t 
onguration in the above way rolling be
ause the 
ir
les tangent to the perturbed 
onguration appear to roll along the surfa
e of the environment. In Figure 3.4, we roll a 
onta
t 
onguration independently of all oth- ers. We now exploit the fa
t that we 
annot independently roll a 
onta
t 
onguration in general. As the path deforms, its des
ription outlined in Corollary 3.3 
hanges. Typi
ally, these 
hanges in the des
ription are 
ontinuous (i.e. only the 
onta
t 
on- gurations 
hange), but o

asionally the 
hanges are dis
ontinuous (for example, the number of jumps in the 
anoni
al representation in
reases). Whenever a dis
ontinuity o

urs, there is a 
orresponding 
hange in the stru
ture of the path. At this point, we 
onstrain the path to preserve this new stru
ture. This 
onstraint has a dis
rete des
ription be
ause it refers to the stru
ture of the path, whi
h is 
ombinatorial. In- sisting that the path satisfy su
h a 
onstraint ee
tively removes a degree of freedom. Eventually the path is over 
onstrained and no 
onta
t 
onguration 
an 
hange. At this point, ea
h 
onta
t 
onguration is uniquely determined by the 
onstraints that we impose on the path. Hen
e, the resulting path has a purely dis
rete des
ription. To be more formal, when we roll a 
onta
t 
onguration, we perturb it 
ontinuously while maintaining 
onta
t with a spe
i
 feature: at a 
orner, the 
onguration will rotate about that 
orner (see Figure 3.4(a)); at a wall, the 
onguration will tra
e a 
ontinuous path along that wall (see Figure 3.4(b)). Our insisten
e that rolling is 
ontinuous allows us to keep a path feasible during normalisation: rolling a 
onguration 
auses the path to deform 
ontinuously; by 
ontinuity, if ex
essive rolling makes a path infeasible, there is a smaller amount of rolling su
h that (a) the path is feasible and 28 (b) rolling it an arbitrarily small amount more makes it infeasible; at this point, we introdu
e a 
onstraint to ensure that any future rolling keeps the path feasible. One way that we 
onstrain a path is by de
laring a 
onta
t 
onguration stati
. We refer to su
h a 
onguration as an an
hor be
ause we never roll it. To see one way that we use an
hors, note that we 
annot roll a 
onguration indenitely (see Figure 3.4): at a 
orner, if we pivot too mu
h, the 
onta
t 
onguration will be dire
ted into an obsta
le (whi
h 
annot o

ur on a feasible path); at a wall, if we slide too far, the 
onta
t 
onguration will no longer tou
h the wall. We 
all the 
ongurations that bound the safe range of rolling at a feature type 1 an
hors. There are O(n1) type 1 an
hors: O(1) at ea
h of O(n) features. By de
laring these extreme 
ongurations an
hors, we know that we 
an safely roll a non-an
hor 
onta
t 
onguration. The other way that we 
onstrain a path is by restri
ting the length of a segment on a jump J in its 
anoni
al representation, as summarised by the next two invariants: 1. on
e an L-segment of J has zero length, that segment of J always has that length; and 2. on
e a C-segment of J has zero or π length, that segment of J always has that length. To re
ord the 
onstraints due to these invariants, we further rene our notion of stru
- ture: we augment ea
h letter of the signed stru
ture with a subs
ript indi
ating its length (examples follow shortly). When the length of a C-segment is zero, the C- segment's orientation is irrelevant, so we omit the 
orresponding supers
ript. We 
all the resulting sequen
e the ne stru
ture. The above invariants imply that the ne stru
ture of a jump in the 
anoni
al representation of a path always be
omes more spe
i
. We take two dierent approa
hes to maintaining length restri
tions. If a jump on the 
anoni
al representation is over 
onstrained (at least two of its segments have a length 
onstraint), we keep the jump stati
 with a new type of an
hor 1 : a type 2 an
hor is the rst or last 
onguration of an over-
onstrained jump. There are O(n2) type 2 an
hors  O(n) possible features to leave from, O(n) possible features to arrive at, and O(1) possible link types. If a jump on the 
anoni
al representation is singly-
onstrained (only one of its segments has a length 
onstraint), we maintain the jump's length 
onstraint by insisting that the rst and last 
onguration of a jump roll simultaneously. We refer to a 
onstrained jump (either singly- or over-
onstrained) as a link be
ause the jump's 
onstraints establish a homeomorphism (a 
ontinuous fun
tion with a 
ontinuous inverse) between the rst and last 
onguration of that jump. We denote the type of a link by its ne stru
ture. To maintain length the 
onstraints asso
iated with a link, we must simultaneously roll the rst and last 
ongurations of that link. A 
hain is a sequen
e of 
ongurations where 
onse
utive 
ongurations are joined by a link. We say that two 
ongurations 1 A C0LC0 jump along a wall is the one ex
eption to this rule: we 
an typi
ally roll both 
ongu- rations without 
hanging the jump's ne stru
ture, so we do not keep this type of jump stati
. 29 are 
hained to ea
h other if they are part of the same 
hain. This denition is important be
ause if θ is 
hained to ψ, then θ and ψ must roll simultaneously or not at all. We note that being 
hained denes an equivalen
e relation between 
onta
t 
ongurations: θ is trivially 
hained to θ by a 
hain of length one; θ is 
hained to φ if and only if φ is 
hained to θ; and if θ is 
hained to φ and φ is 
hained to ψ, then θ is 
hained to ψ. The equivalen
e 
lasses of this relation are the maximal 
hains of the path. If we roll a 
onguration θ, we must simultaneously roll every 
onguration that is 
hained to θ. Hen
e, if θ is 
hained to an an
hor, we 
annot roll θ. In this 
ase, we say that θ is moored. Note that every an
hor is moored (by a 
hain of length one), but not every moored 
onguration is an an
hor. Moored 
ongurations are important be
ause they have a dis
rete des
ription: an moored 
onguration θ is determined by an an
hor and a 
hain of links leading to that an
hor, ea
h of whi
h has a dis
rete des
ription. The next two examples illustrate how we roll unmoored 
onta
t 
ongurations to make them moored. In Figure 3.5(a), we roll 
ongurationW in a 
ounter
lo
kwise manner about 
orner w until the L-segment on the jump from V to W vanishes. At this point, the jump from V and W is a C+L0C − -type link. In Figure 3.5(b), we simultaneously roll V and W be
ause 〈V,W 〉 is a 
hain. We do this until the rst C-segment on the jump from U to V vanishes. At this point, the jump from U to V is a C0LC + -type link. In Figure 3.5(
), we simultaneously roll U , V , and W be
ause 〈U, V,W 〉 is a 
hain. We do this until a C-segment tou
hes 
orner t. At this point, U is type 2 an
hor be
ause the jump from t to u is over-
onstrained. Hen
e,W is moored be
ause 〈U, V,W 〉 is a 
hain. WV U w v u (a) A link from V to W forms. W V U wv u (b) A link from U to V forms. U V W w v u T t (
) The 
hain 〈U, V,W 〉 be- 
omes moored. Figure 3.5: As we roll W in a 
ounter
lo
kwise dire
tion, we introdu
e 
onstraints whi
h 
ause a 
hain to grow. In Figure 3.6(a), we roll S 
ounter
lo
kwise about s until the L-segment on the jump from S to U tou
hes t. At this point the jump from S to U is non-
anoni
al: in the 
anoni
al representation of the path, the path from S to U is de
omposed into a C−LC0-type link from S to T and a C0LC+-type link from T to U . In Figure 3.6(b), we simultaneously roll S, T , and U be
ause 〈S, T, U〉 is a 
hain. We do this until the rst C-segment on the jump from U to W be
omes exa
tly π long. At this point, the jump from U to W is C+pi LC − -type link. In Figure 3.6(
), we simultaneously S, T , U , and W be
ause 〈S, T, U,W 〉 is a 
hain. We do this until the rst C-segment on the jump from U to W tou
hes v. At this point, the jump from U to W is non-
anoni
al: 30 in the 
anoni
al representation, it splits into a jump from U to V (with ne stru
ture C+L0C0) and a jump from V to W (with ne stru
ture C +LC−). The jump from U to V is over-
onstrained, so the 
ongurations U and V are type 2 an
hors. Hen
e S is moored be
ause 〈S, T, U〉 is a 
hain and U is an an
hor. S s t u U w W T v (a) The un
onstrained jump from S to U be
omes non- 
anoni
al. S s t u U w W T v (b) A link from U toW forms. S s t u U w W V T v (
) A new 
hain forms and S be
omes moored. Figure 3.6: If we roll S in a 
ounter
lo
kwise dire
tion, it eventually be
omes moored. In Figure 3.6(
), the 
ongurations S and W are no longer 
hained when a new 
onta
t o

urs at v be
ause the new jump from V to W is un
onstrained. We nd this new un
onstrained jump problemati
 be
ause it suggests that W does not have a dis
rete des
ription (W is not 
hained to anything other than itself). However, the (non-
anoni
al) jump from U to W is a singly-
onstrained link and U is an an
hor. So W does have a dis
rete des
ription, if we use a non-
anoni
al representation of the path. To 
apture this fa
t in a way that is 
onsistent with our 
anoni
al path representation, we introdu
e a new 
lass of type 3 an
hors: the rst and last 
ongurations of a non- 
anoni
al link. Ea
h type 3 an
hor has a dis
rete des
ription be
ause the interior of every non-
anoni
al link tou
hes an obsta
le whi
h over-
onstrains the link. There are O(n3) type 3 an
hors: there are O(1) dierent types of links, O(n) features the link 
an leave from, O(n) features the link 
an arrive at, and O(n) features that the interior of the link 
an tou
h. In the examples above, we rolled a 
onguration until (a) a 
onguration be
ame an an
hor, (b) a previously 
anoni
al jump be
ame non-
anoni
al, or (
) the length of a segment on a jump of the 
anoni
al representation degenerated. We 
all these types of events path degenera
ies. In the last example, we saw that rolling a 
onguration until a degenera
y o

urs may break a 
hain. However, the 
ongurations in that 
hain were still related. Lemma 3.4. Let 〈θi〉 be a 
hain. After rolling a 
onguration until a degenera
y o

urs, 〈θi〉 may no longer be a 
hain. However, 〈θi〉 still satises an important 
ondition: θj is moored if and only if θl is moored. Proof. If 〈θi〉 is still a 
hain when we quit rolling, this lemma is obviously true. However, 〈θi〉 will break and no longer be a 
hain, if a link between two 
onse
utive 
onta
t 31 
ongurations on 〈θi〉 be
omes non-
anoni
al. This is the 
ase that we now 
onsider. We assume without loss of generality that j ≤ l . The proof of this lemma is indu
tive on l. If j = l, this is trivially true. So 
onsider the 
ase when j < l. As an indu
tion hypothesis, assume that θj is moored if and only if θl−1 is moored. To prove the indu
tive step, we 
onsider two 
ases. If the jump J from θl−1 to θl is 
anoni
al, then J is a link be
ause we preserve the length restri
tions on ea
h link while rolling. Hen
e, θl−1 is moored if and only if θl is moored. Thus, θj is moored if and only if θl is moored by our indu
tive hypothesis. If the jump from θl−1 to θl is non-
anoni
al, then θl−1 and θl are both type 3 an
hors. By our indu
tive hypothesis, θj is moored be
ause θl−1 is an an
hor. Trivially, our indu
tive step holds be
ause θj and θl are both moored. As one of our previous examples showed (see Figure 3.6), the number of non-an
hor 
onta
t 
ongurations may in
rease, but only in a very parti
ular manner. Lemma 3.5. Let J be a 
anoni
al jump on a path. If J be
omes non-
anoni
al due to rolling, then 1. the interior of J 
ontains at most one non-an
hor 
onta
t 
onguration; and 2. if the interior of J 
ontains a non-an
hor 
onta
t 
onguration, then every jump in the 
anoni
al representation of J is a link. Proof. New 
onta
t 
ongurations on a C-segment of J are type 1 an
hors. So any new non-an
hor 
onta
t 
ongurations must o

ur on the interior of L-segment of J . If there is more than one 
onta
t on the L-segment of J , then all of the 
onta
t 
ongurations on the L-segment are type 1 an
hors. This proves 
laim 1. To see 
laim 2, suppose that the interior of the L-segment of J tou
hes an obsta
le at p. Then the interior of every 
anoni
al jump K 
ontained in J does not 
ontain p. Hen
e, either the rst or the last C-segment of K has zero-length. Therefore, K is a link. Rolling an unmoored 
onguration makes the des
ription of a path more dis
rete, but it does so at the expense of in
reasing the size of its 
anoni
al representation. The next lemma quanties this trade-o. Lemma 3.6. Let Π be a FW-normal path. If we roll a 
onguration until a degenera
y o

urs, we in
rease the number of non-an
hor 
ongurations on Π by at most two and we de
rease the number of unmoored maximal 
hains of Π by at least one. Proof. We rst show that the number of non-an
hor 
ongurations in
reases by at most two. As we roll a 
onguration θ, we simultaneously roll ea
h 
onguration in the maximal 
hain 〈θi〉 that 
ontains θ. The only parts of Π that deform are the jump pre
eding 〈θi〉, the links between 
onse
utive 
ongurations of 〈θi〉, and the jump following 〈θi〉: ea
h of these jumps hosts at most one new non-an
hor 
onguration by Lemma 3.5; moreover, any interior 
onta
t on the link from θi to θi+1 is a type 3 32 an
hor; hen
e, there are at most two new non-an
hor 
onta
t 
ongurations  one on the jump pre
eding 〈θi〉 and one on the jump following 〈θi〉. We now show that the number of unmoored maximal 
hains de
reases by at least one. Suppose that some θi be
omes moored. Then the number of unmoored maximal 
hains drops by at least one be
ause ea
h θi is moored (see Lemma 3.4) and all new 
onta
t 
ongurations are moored: any new 
onta
t 
ongurations on the link from θi to θi+1 are an
hors, and any new 
onta
t 
ongurations on the jump pre
eding or pro
eeding 〈θi〉 are moored (see Lemma 3.5). Suppose that no θi be
omes moored. Then 〈θi〉 is still an unmoored 
hain: the link from θi to θi+1 is still 
anoni
al be
ause θi is not type 3 an
hor. Hen
e, either the jump pre
eding 〈θi〉 or the jump pro
eeding 〈θi〉 degenerated (be
ame a link or non-
anoni
al). In either 
ase, the 
hain 〈θi〉 merges with another 
hain: if the jump pre
eding 〈θi〉 degenerated, then 〈θi〉 merges with the 
hain pre
eding it; otherwise 〈θi〉 merges with the 
hain pro
eeding it. If 〈θi〉 merges with an moored maximal 
hain, then 〈θi〉 be
omes moored, whi
h de
reases the total number of unmoored maximal 
hains. Otherwise, two unmoored maximal 
hains merge, redu
ing the total number of unmoored maximal 
hains. We say that a FW-normal path is BK normal if every 
onta
t 
onguration is moored. The 
ompleteness of our normal form is expressed below. Theorem 3.7. Suppose that there is a Dubins path from 
onguration αs to 
ong- uration αt with intri
a
y k. Then there is a BK-normal path Π from αs to αt with O(nk + n3) 
onta
t 
ongurations. Proof. To prove this theorem, we use a potential fun
tion P that assigns a natural number to any FW-normal path Π from αs to αt. Let c(Π) be the number of non- an
hor 
ongurations on Π, d(Π) be the number of unmoored maximal 
hains of Π, and P(Π) = c(Π) + 3d(Π). Now, suppose that some 
hain of Π is unmoored. We 
an redu
e the potential of Π by rolling it until a degenera
y o

urs: by the previous lemma, c(Π) in
reases by at most two and d(Π) de
reases by at least one; hen
e, P(Π) de
reases by at least one. Therefore, if Π is a path from αs to αt with minimum potential, every 
onta
t 
onguration on Π is moored. Not only are low potential paths dis
rete, but they also have bounded intri
a
y. Suppose that there is a Dubins path from αs to αt with intri
a
y k. By Lemma 3.2, there exists a FW-normal path Π from αs to αt with at most O(nk + n 2) 
onta
t 
ongurations. Hen
e, P(Π) = O(nk + n2) be
ause c(Π) = O(nk + n2) and d(Π) = O(nk+n2). Let Π′ be a FW-normal path from αs to αt with minimum potential. Then c(Π′) = O(nk+n2). We assume without loss of generality that no an
hor 
onguration o

urs twi
e on Π′: if it does, Π′ has a loop; if we remove this loop, Π′ is still FW- normal and P(Π′) does not in
rease. Therefore Π′ has O(nk+n3) 
onta
t 
ongurations be
ause there are O(n3) an
hor 
ongurations. Moreover, by the previous paragraph, every 
onta
t 
onguration of Π′ is moored. 33 Chapter 4 Testing Feasibility In this 
hapter, we present two path-planning algorithms. Our rst algorithm exhaus- tively sear
hes the spa
e of BK-normal paths. Our se
ond algorithm prunes this sear
h to ignore paths that are redundant. The major result of this 
hapter is that our se
ond algorithm is both e
ient and 
omplete: let Π be a feasible path that has the least intri
a
y of all feasible paths; then our algorithm will nd a feasible BK-normal path Π′, where the intri
a
y of Π′ is polynomially bounded in the intri
a
y of Π. A motion-planning problem instan
e 
onsists of a set of polygonal obsta
les to avoid, a start 
onguration αs, and a terminal 
onguration αt. The intrinsi
 di
ulty of a problem instan
e is the minimum intri
a
y of a feasible Dubins path from αs to αt. Intuitively, the intrinsi
 di
ulty is a lower bound on the run time of any algorithm that returns a natural des
ription of the path that it nds. Although previous results do not mention intrinsi
 di
ulty, our statement is 
onsistent with them. Take the bounded-
urvature algorithms reviewed in Se
tion 2.2.3 for example: these algorithms work in restri
ted domains; these domain restri
tions imply that the intrinsi
 di
ulty is bounded in terms of the size of the problem instan
e; therefore, the intrinsi
 di
ulty is impli
itly in
luded in the upper bound on the run time as a parameter measuring the size of the input. There is no known bound on the intrinsi
 di
ulty when the obsta
les 
an be arbitrary polygonal obsta
les. So we formulate our bounds in terms of the intrinsi di
ulty. We insist that a parameter k that bounds the intri
a
y of the paths that our algorithms will 
onsider be given as input. Given k, our algorithms will either verify that the intrinsi
 di
ulty is greater than k (no solution is found) or return a feasible solution. If a solution Π is returned, the intri
a
y of Π is polynomially bounded in terms of k and the 
omplexity of the environment n. The main reason that we do not return a path of minimum intri
a
y is that we sear
h for BK-normal paths (see Theorem 3.7). We limit our sear
h to the spa
e of BK-normal paths be
ause it is 
ountable and, hen
e, systemati
ally sear
hable. Our rst algorithm exhaustively sear
hes for a BK-normal paths from αs to αt. In the worst 
ase, its sear
h spa
e may be exponentially large in terms of the environment 
omplexity n. To improve e
ien
y, we identify a form of redundan
y and prune our 34 sear
h to ignore redundant paths. To leverage this redundan
y, we allow a 
onstant fa
tor in
rease in intri
a
y: the path found by our algorithm with pruning is at most a 
onstant fa
tor more 
omplex than the path found by our exhaustive algorithm. When we des
ribe our pruned sear
h, we omit the subroutine that does the pruning. Instead, we spe
ify a property that we want it to satisfy. This property is su
ient to guarantee that it does not prune too mu
h. It is always possible to satisfy this property: it is trivially satised by not pruning anything. The next 
hapter explains how we prune. At that time, we prove that pruning is both e
ient and ee
tive. 4.1 Exhaustive Sear
h The path-nding algorithm that we present in this se
tion performs an exhaustive sear
h for a BK-normal paths. We exploit the fa
t that we just want to nd one solution to a planning problem, not every solution. Spe
i
ally, we break the problem into smaller subproblems and 
ombine one solution to ea
h subproblem to get the desired solution to the problem. αs αt α1 α2 (a) This path is an (αs, α1)-linkage, followed by an (α1, α2)-linkage, followed by an (α2, αt)- linkage. αs α1 α2 αt 1 0 2 (b) Path in the an
hor graph 
orresponds to a BK-normal path. Figure 4.1: Linkages and an
hor graphs. If we split any BK-normal path at its an
hors, ea
h resulting subpath is BK-normal, starts at an an
hor, ends at an an
hor, and is internally free of an
hors (see Fig- ure 4.1(a)). We 
all su
h a path from an an
hor α to an
hor α′ an (α, α′)-linkage. This denition implies that a BK-normal path from αs to αt is 
omposed of a unique sequen
e of linkages. Our path-nding algorithm has two phases: we rst sear
h for a linkage between ea
h pair of an
hors; then we sear
h for a path from αs to αt by 
ombining the linkages that we found. During the rst phase, we 
onstru
t a dire
ted weighted graph 
alled an an
hor graph. Ea
h vertex 
orresponds to an an
hor and ea
h edge 
orresponds to a feasible linkage. The weight of an edge is the number of non-an
hor 
onta
t 
ongurations on the linkage asso
iated with that edge. We are 
areful to nd linkages that minimise the weight of ea
h edge. In the se
ond phase, we nd the minimum weight path P from αs to αt in the an
hor graph (see Figure 4.1(b)). By 
on
atenating the linkages asso
iated with ea
h 35 edge of P , we re
over a BK-normal path Π from αs to αt. The path Π has the fewest non-an
hor 
onta
t 
ongurations possible by our 
hoi
e of P and 
onstru
tion of the an
hor graph. Fa
t 4.1. If there is a feasible Dubins path from αs to αt with intri
a
y k, there exists a path in the an
hor graph with weight O(nk). Proof. This follows from 
loser examination of the proof of Lemma 3.2 and Theorem 3.7. Spe
i
ally, given the ante
edent, the proof of Lemma 3.2 implies the existen
e of a feasible FW-normal path from αs to αt with O(nk) non-an
hor 
onta
t 
ongurations. This implies the existen
e of a feasible BK-normal path Π from αs to αt with O(nk) non-an
hor 
ongurations by the proof of Theorem 3.7. This path Π 
orresponds to a path in the an
hor graph with weight O(nk). To 
onstru
t our an
hor graph, we need to nd linkages between an
hors. To nd linkages, we exploit their stru
ture. Let Π be a (α, α′)-linkage. Ea
h 
onta
t 
ong- uration of Π is either 
hained to α or α′ be
ause Π is BK-normal and internally free of an
hors. This allows us to split Π into a 
hain starting with α, a 
hain ending in α′, and a jump from the former to the latter. Based on this observation, we sear
h for a (α, α′)-linkage by attempting to bridge every 
hain starting with α to every 
hain ending with α′ by a single jump. This redu
es our problem of nding a (α, α′)-linkage to nding 
hains starting with α and nding 
hains ending with α′. To nd 
hains starting with α, we iteratively extend by one link those 
hains that we have already found. The details of this pro
edure depend on our representation of 
hains. Re
all that we want to nd linkages with the minimum number of non- an
hor 
onta
t 
ongurations. This is a
hieved by nding 
hains that rea
h a parti
ular 
onguration with the minimum number of links. Hen
e, we only need to know a few things about ea
h 
hain: where it starts, where it ends, and how many links it takes to get from its start to its end. To this end, let Φα,Fl denote the set of all 
onta
t 
ongurations at feature F that are rea
hed by a 
hain of l links from an an
hor α. We build the sets Φα,Fl in
rementally using a pro
edure named Propagate: the pro
edure 
all Propagate(Φα,Fl ) adds a 
onguration φ ′ to Φα,Gl+1 whenever there exists a 
onguration φ in Φα,Fl that rea
hes a 
onguration φ ′ at G via a single feasible link. Similarly, we denote with Ψα,Fl the set of all 
onta
t 
ongurations at feature F that rea
h α by a 
hain of l links. We do not expli
itly 
onstru
t Ψα,Fl be
ause we 
an 
reate it in a way similar to Φα,F : to see the symmetry between the two sets, note that a 
hain ending with α is the reverse of a 
hain beginning with the ree
tion of α. Figure 4.2 
ontains the pseudo-
ode for a pro
edure AllLinkages that 
onsiders linkages with at most τ non-an
hor 
onta
t 
ongurations. Sin
e 
he
king if a given L- or C-segment avoids all obsta
les 
an be done in O(n) time, it is straightforward to 
onrm that pro
edure AllLinkages 
an be implemented to run in time that is polynomial in the total number of 
ongurations generated by propagation. 36 AllLinkages(τ) 1 initialise Φα,F0 for all α and F for all an
hors α do for l = 0 to τ − 1 do for all environment features F do Propagate(Φα,Fl ) 2 for all pairs of an
hors α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su
h that l + l′ ≤ τ do determine if there exist 
ongurations φ ∈ Φα,Fl and ψ ∈ Ψα′,F ′l′ su
h that: (i) there is a feasible jump joining φ and ψ, and (ii) the (α, α′)-linkage through φ and ψ has fewer non-an
hor 
onta
t 
ongurations than any (α, α′)-linkage found so far. Figure 4.2: Algorithm that exhaustively 
onsiders all linkages with at most τ non- an
hor 
onta
t 
ongurations. It re
ords the (α, α′)-linkage with fewest non-an
hor 
onta
t 
ongurations found, for ea
h pair of an
hors (α, α′). 4.2 Redundan
y Elimination The run time of the algorithm in Figure 4.2 is dominated by the time taken to 
onstru
t the various Φα,Fl . Re
all that ea
h of these sets represent 
hains: φ ∈ Φα,Fl if there exists a feasible l-link 
hain starting with α and ending at feature F with 
onguration φ. We use φ inter
hangeably to refer to a 
onguration and the 
hain that rea
hes φ. Whi
h of these will be 
lear from 
ontext. To nd 
hains starting with an an
hor, we iteratively extend the 
hains that we have already found by one more link. During this pro
ess, the same 
hain may be extended by O(n) distin
t links be
ause there are O(n) features that 
an be rea
hed by a link. Su
h an un
he
ked proliferation of 
hains 
ould generate O(n)O(nk) 
hains be
ause we generate all 
hains with O(nk) links. In this se
tion, we argue that it su
es to 
al
ulate a subset Φ̂α,Fl of Φ α,F l , if we permit a 
onstant fa
tor in
rease in intri
a
y. To be pre
ise, if our algorithm that 
onstru
ts Φα,Fl nds a path with c non-an
hor 
onta
t 
ongurations, our algorithm that 
onstru
ts Φ̂α,Fl will nd a path with O(c) non-an
hor 
onta
t 
ongurations. The gist of our argument justifying our 
onstru
tion of Φ̂α,Fl instead of Φ α,F l is simple: any time a 
hain in Φα,Fl o

urs on a path, we 
an repla
e it by a 
hain in Φ̂α,Fl . The details of this argument are 
ompli
ated by the fa
t that it is unlikely that two 
hains share the same beginning and ending 
onguration. So rather than a simple substitution of one 
hain for another, we are going to use a more sophisti
ated pro
edure. Spe
i
ally, we are going to remove one 
hain, add the other 
hain, and 37 φ′ l φl+1 JF G (a) φ′l rea
hes φl+1 via J . φ′ l φl+1 J K F G (b) φ′l rea
hes φl+1 via J and K. φ′ l φl+1 J K F G (
) φ′l rea
hes φl+1 via K and J . Figure 4.3: In ea
h instan
e, the 
hain φ′l (solid dark) dire
tly rea
hes the 
hain φl+1 (gray). then use one or two additional jumps as putty to ll in any remaining gap. In general, this substitution still may not be possible, so we use a pre
ise phrase to denote when it is possible. Spe
i
ally, whenever we 
an append one 
hain φ′l with at most one jump J and one link K to 
reate a path that begins and ends at the same 
ongurations as φl+1, we say that φ ′ l almost spans φl+1. Figure 4.3 illustrates several dierent situations where φ′l almost spans φl+1. When nding 
hains that start with an an
hor, we want to avoid produ
ing re- dundant 
hains. We do this with a pro
edure Filter, whi
h we periodi
ally 
all to remove redundant 
hains (see Figure 4.4). This 
ulling prevents the potential explosion noted earlier. We leave the des
ription of Filter to the next 
hapter. For now, we just des
ribe the essential property of its output. To do this, we need to distinguish between the 
hains that Filter removes (unviable 
hains) and those that it does not (viable 
hains). Completeness Property: If φl ∈ Φ̂α,Fl is unviable, then ea
h one link extension φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . 38 AllViableLinkages(τ) 1 initialise Φ̂α,F0 for all α and F for all an
hors α do for l = 0 to τ − 1 do for all environment features F do if l is divisible by 4 then Φ̂α,Fl ← Filter(Φ̂α,Fl ) Propagate(Φ̂α,Fl ) 2 for all pairs of an
hor 
ongurations α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su
h that l + l′ ≤ τ do determine if there exist φ ∈ Φ̂α,Fl and ψ ∈ Ψ̂α′,F ′l′ su
h that: (i) there is path Π from φ to ψ 
onsisting of at most 8 links and one jump, and (ii) φ+Π + ψ has fewer non-an
hor 
onta
t 
ongurations than any (α, α′)-linkage found so far. Figure 4.4: Filtering 
ongurations before propagation. The result of repla
ing an unviable 
hain with a viable 
hain that almost spans it may not be BK-normal. The next lemma shows that an unviable 
hain is still redundant when we restri
t our attention to BK-normal paths. Essentially, it states that if there exists a (α, α′)−linkage Λ that starts with an unviable prex, then there exists a feasible BK-normal path P from α to α′ that starts with a viable prex of roughly the same intri
a
y as Π. This lemma in
ludes several 
onditions that highlight the important similarities and dieren
es between Π and P . These details are used in a later theorem. Lemma 4.2. Let φl+1 be an one link extension of an unviable 
hain φl of Φ̂ α,F l . If φl+1 is the prex of some (α, α′)-linkage Λ, there exists a BK-normal path P from α to α′ su
h that 1. a viable 
hain φ′l of Φ̂ α,F l is the prex of P , 2. the sux of Λ is a sux of P , and 3. P has at most three more non-an
hor 
onta
t 
ongurations than Λ. Proof. By the Completeness Property, there exists a viable 
hain φ′l of Φ̂ α,F l su
h that φ′l almost spans φl+1. Let Λ ′ be the result of repla
ing φl+1 with φ ′ l and at most one jump J and one link K (see Figure 4.3). It is straightforward to verify that (a) Λ′ has at most one more non-an
hor 
onguration than Λ and (b) Λ′ has at most one unmoored maximal 
hain (be
ause J is an arbitrary jump). Note that Λ′ satises 39 the three 
onditions of this theorem. However, the possible existen
e of an unmoored maximal 
hain prevents Λ′ from being BK-normal. Let P be the result of rolling su
h an unmoored maximal 
hain until it degenerates. By Lemma 3.6, P has at most two more non-an
hor 
onta
t 
ongurations than Λ′. Hen
e, the third 
ondition of this lemma is satised. Moreover, the moored 
onta
t 
ongurations of Λ′ are un
hanged by this operation. Therefore, the rst and se
ond 
onditions of this lemma hold as well. With the pre
ise notion of redundan
y given in the previous lemma, we are able to prove that AllViableLinkages 
an be used to nd a feasible path. Theorem 4.3. Suppose that there exists a feasible Dubins path from αs to αt with intri
a
y k. Then there exists a feasible BK-normal path Π∗ from α to αt su
h that 1. Π∗ has O(nk + n3) 
onta
t 
ongurations, and 2. every linkage in Π∗ is found by AllViableLinkages. Proof. To quantify the extent to whi
h a BK-normal path Π from αs to αt satises this theorem, we assign a non-negative integer potential, denoted P(Π). We argue that a BK-normal path Π∗ with minimum potential satises this theorem. The rst term 
ontributing to P(Π) is proportional to the number of non-an
hor 
ongurations on Π, denoted c(Π). The se
ond term 
ontributing to P(Π) is propor- tional to the viability of Π, denoted v(Π), that is a measure of how mu
h of the path is found through 
onguration propagation. The potential P(Π) is 5c(Π)− 4v(Π). To 
al
ulate v(Π), we sum the viability of its 
onstituent linkages. Let Λ be one su
h (α, α′)-linkage and v(Λ) denote its viability. Re
all that Λ 
an be de
omposed into a 
hain φ starting at α, followed by a jump J , followed by a 
hain ψ ending at α′. Let φi denote the i-link prex of φ. Then the largest i, denoted v(φ), su
h that φi is viable measures how mu
h of φ is found by AllViableLinkages. Although φv(φ) is viable, it may not have been subje
ted to the pro
edure Filter be
ause AllViableLinkages only 
alls Filter(Φ̂α,Fl ) when l is a multiple of four. To this end, let v ′(φ) = 4⌊v(φ)/4⌋. Then φv′(φ) is the longest viable prex of φ that is ltered. We dene v ′(ψ) analogously. Finally, we dene v(Λ) as v′(φ∗) + v′(ψ∗), where φ∗, J , and ψ∗ are a de
omposition of Λ that maximises v′(φ∗) + v′(ψ∗). Let Π∗ be a feasible BK-normal path from αs to αt with minimum potential. Su
h a path exists be
ause (a) there are feasible BK-normal paths from αs to αt and (b) the potential of a path is always non-negative. Condition (a) follows from Theorem 3.7. Condition (b) is satised be
ause c(Π) ≥ 0, v(Π) ≥ 0, and c(Π) ≥ v(Π). The last 
laim is 
ru
ial and bears further examination: 
learly c(Π) = ∑ Λ∈Π c(Λ) and v(Π) =∑ Λ∈Π v(Λ), where Λ ∈ Π means that Λ is a linkage of BK-normal path Π; hen
e, it su
es to show that c(Λ) ≥ v(Λ), for ea
h Λ; to see this, note that c(Λ) + 1 is the number of jumps on the 
anoni
al representation of Λ and v(Λ) + 1 is at most the number of jumps on the 
anoni
al representation of Λ. 40 Suppose for 
ontradi
tion that AllViableLinkages did not nd one of the link- ages between an
hors on Π∗. Let Λ be an (α, α′)-linkage of Π∗ that is not found by our algorithm. We now argue that there exists a BK-normal path P from α to α′ su
h that P(P ) < P(Λ). This is impossible be
ause if we repla
e Λ with P on Π∗, we 
reate a path with lower potential than Π∗, a 
ontradi
tion. To nd P , we rst de
ompose Λ into the 
hain φ, jump J , and ψ that maximises v(φ) + v(ψ). The subpath of Λ joining φv′(φ) and ψv′(ψ) has at least 9 links be
ause AllViableLinkages did not nd Λ. Hen
e, either φ is at least 5 links longer than φv′(φ) or ψ is at least 5 links longer than ψv′(ψ). Suppose the former (the latter 
ase is symmetri
). Then φv′(φ)+4 is unviable by denition of v ′(φ). Moreover, φv′(φ)+5 is a prex of Λ. Hen
e, we 
an apply Lemma 4.2: let P be a BK-normal path α to α′ su
h that (a) P has viable [v(φ) + 4]-link prex, (b) ψv′(ψ) is a sux of P , and (
) c(P ) ≤ c(Λ) + 3. Conditions (a) and (b) imply that v(P ) ≥ v(Λ) + 4. Thus P(P ) ≤ 5[c(Λ) + 3]− 4[v(Λ) + 4] = P(Λ)− 1. We now bound the number of non-an
hor 
ongurations on Π∗. By Theorem 3.7, there exists a BK-normal path Π from αs to αt with O(nk) non-an
hor 
onta
t 
ong- urations. Hen
e, P(Π) ∈ O(nk) be
ause P(Π) ≤ 5c(Π). Therefore, P (Π∗) ∈ O(nk). Note that P (Π∗) ≥ c (Π∗) be
ause c (Π∗) ≥ v (Π∗). Thus c (Π∗) ∈ O(nk). If an an
hor 
onguration o

urs twi
e on Π∗, we 
an remove the asso
iated loop without in
reasing the potential of Π∗. Therefore, we 
an assume without loss of gen- erality that no an
hor o

urs twi
e on Π∗. In this 
ase, the number of 
onta
t 
ongu- rations on Π∗ is c(Π∗) +O(n3) = O(nk + n3). 41 Chapter 5 Eliminating Redundan
y In the previous 
hapter, we dis
ussed two path-planning algorithms that grow paths of in
reasing intri
a
y until the set of dis
overed paths is ri
h enough that it must 
ontain a solution, if the problem admits a solution of su
iently low intri
a
y. The rst path- planning algorithm is exhaustive, whereas the se
ond path-planning algorithm prunes its sear
h. To be more pre
ise, the rst algorithm 
al
ulates the entire set Φα,Fl of l-link 
hains an
hor α to feature F , whereas the se
ond algorithm only 
al
ulates a subset Φ̂α,Fl of Φ α,F l . We generate Φ α,F l and Φ̂ α,F l in similar manners. To 
al
ulate Φ α,G l , we 
onsider every one link extension to G of every 
hain in every Φα,Fl−1 . To 
al
ulate Φ̂ α,G l , we 
onsider every one link extension to G of every viable 
hain in every Φ̂α,Fl−1 , where a 
hain is viable if it is not removed by ltering. Re
all that we insist that unviable 
hains redundant with respe
t to viable 
hains, as formalised in the following 
ondition. Completeness Property: If φl ∈ Φ̂α,Fl is unviable, then ea
h one link extension φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . In this 
hapter, we lter Φ̂α,Fl in a way that satises the Completeness Property. We start with two 
ases where we 
an satisfy the the Completeness Property in a straight- forward manner. Then, we dis
uss a third 
ase where we satisfy the Completeness Property indire
tly. In this 
ase, we rely on several te
hni
al results that we prove in Appendi
es A and B. In this 
hapter, we also argue that our ltering is polynomially bounded. Spe
i
ally, we show that ltering Φ̂α,Fl takes time that is polynomially bounded in |Φ̂α,Fl | and n. Moreover, we show that the number of resulting viable 
ongurations is polynomially bounded in n, m, and l. To prove this result, we rely on some te
hni
al results that we prove in Appendix C. These two 
onditions imply that the run time of our se
ond algorithm is polynomially bounded in n, m, and k. We ta
kle the problem of ltering Φ̂α,Fl with a divide-and-
onquer approa
h. Spe
if- i
ally, we identify dierent types of one-link extensions of Φ̂α,Fl . We dene the extension types so that extensions of a parti
ular type are so similar that we 
an solve the asso- 
iated subproblem with one simple strategy. To 
larify what we mean by subproblem, for ea
h type of extension T , we sele
t a subset Φ̂α,Fl [T ] of Φ̂ α,F l so that every one-link 42 extension of Φ̂α,Fl of type T is almost spanned by some 
hain in Φ̂ α,F l [T ]. The result of ltering Φ̂α,Fl is the union ⋃ T Φ̂ α,F l [T ]. This union satises the Completeness Property be
ause our 
hoi
e of types types is exhaustive: every one-link extension of Φ̂α,Fl is of some parti
ular type. 5.1 Filtering with Walls We rst address the easiest 
ase: suppose that we want to lter Φ̂α,Fl when F is a wall. In this instan
e, we use the fa
t that on
e we rea
h a wall, we 
an follow that wall unimpeded. To be more pre
ise, let φl, φ ′ l ∈ Φ̂α,Fl be two 
ongurations at F oriented in the same dire
tion. If φ′l 
omes before φl, then φ ′ l 
an rea
h φl by following F (see Figure 4.3(b)). Hen
e, φ′l almost spans every one link extension of φl. Therefore, we 
an eliminate all but the two 
hains of Φ̂α,Fl that rea
h F the earliest in ea
h dire
tion and still satisfy the Completeness Property. Now, suppose that we want to lter Φ̂α,Fl when F is a 
orner. In this 
ase, we distinguish the extensions of Φ̂α,Fl by the feature G that they rea
h. For ea
h G, we identify a subset Φ̂α,Fl [G] of Φ̂ α,F l so that for every one link extension φl+1 of φl ∈ Φ̂α,Fl to G, there exists φ′l ∈ Φ̂α,Fl [G] su
h that φ′l almost spans φl+1. Suppose that we want to identify Φ̂α,Fl [G] when G is a wall. Again, we use the fa
t that on
e we rea
h a wall, we 
an follow the wall unimpeded. Spe
i
ally, let φl, φ ′ l be 
hains of Φ̂α,Fl and φl+1, φ ′ l+1 be one link extensions to G of φl and φ ′ l respe
tively. If φl+1 and φ ′ l+1 are oriented the same way and φ ′ l+1 rea
hes G before φl+1 at G, then φ′l+1 
an follow G to rea
h φl+1 (see Figure 4.3(
)). In this 
ase, φ ′ l almost spans φl+1. Hen
e, we sele
t at most two 
hains for Φ̂α,Fl [G]: the 
hains of Φ̂ α,F l that rea
h G via a one link extension the earliest. 5.2 Corner to Corner Extensions In the 
ases that we just addressed, we used the fa
t that one 
hain 
an rea
h a range of 
ongurations via a single jump. In parti
ular, on
e we rea
h a wall, we 
an follow that wall unimpeded. We now address the problem of 
onstru
ting Φ̂α,Fl [G], when both F and G are 
orners. In this 
ase, we use the fa
t that one 
onguration at F 
an rea
h a range of 
ongurations at G via a single jump (see Figure 5.1(a)). This rea
h is dierent from the rea
h along a wall in two important ways: an obsta
le may blo
k a jump from F to G, whereas the jump along a wall is free of obsta
les; and the rea
h from F to G shifts (see Figure 5.1(b)), whereas the rea
h at a wall grows monotoni
ally (the earlier you rea
h the wall, the better). First, we formalise what we mean by the rea
h from F to G with a 
ouple of denitions. The spe
trum of jumps rea
hing G from one 
onguration φ at F is the set of all jumps from φ to G, in
luding jumps blo
ked by obsta
les (see Figure 5.1(a)). By allowing jumps in a spe
trum to 
ollide with obsta
les, a jump spe
trum only depends 43 on φ and the relation of φ to G (see Figure 5.1(b)). The rea
h of a jump spe
trum from φ to G, denoted reach(φ), is the set of all destination 
ongurations rea
hed by some jump in that spe
trum. F G (a) One 
onguration at F rea
hes a range of 
ongurations at G via a single jump. φ2 φ3 φ1 F G (b) The range of 
ongurations rea
hed at G depends on the sour
e 
onguration at F . Figure 5.1: Jump spe
tra. We now des
ribe how to sele
t Φ̂α,Fl [G] so that for every one-link extension φl+1 of φl ∈ Φ̂α,Fl , there exists φ′l ∈ Φ̂α,Fl [G] su
h that there is a feasible jump from φ′l to φl+1 (in whi
h 
ase, φ′l almost spans φl+1). We guarantee the existen
e of a jump from φ ′ l to φl+1 with jump spe
tra: there exists a jump from φ ′ l to φl+1, if φl+1 ∈ reach(φ′l). However, this guaranteed jump from φ′l to φl+1 may be infeasible be
ause jumps in a spe
trum 
an be blo
ked by obsta
les. To guarantee that this jump is 
ollision-free, we introdu
e new subproblems. In our new subproblems, we distinguish the extensions of Φ̂α,Fl by the feature G that they rea
h, their ne stru
ture Γ, and their homotopy 
lass h. For ea
h G, Γ, and h, we identify a subset Φ̂α,Fl [G,Γ, h] of Φ̂ α,F l so that for every one link extension φl+1 of φl ∈ Φ̂α,Fl to G with ne stru
ture Γ and homotopy h, there exists φ′l ∈ Φ̂α,Fl [G,Γ, h] su
h there exists a feasible jump from φ′l to φl+1. Then we take the union of the solutions to the subproblems ⋃ Γ,h Φ̂ α,F l [G,Γ, h] as the desired Φ̂ α,F l [G]. We 
hoose Φ̂α,Fl [G,Γ, h] with a greedy approa
h. Initially, we set Φ̂ α,F l [G,Γ, h] to the 
ongurations of Φ̂α,Fl that 
an rea
h G via a link with ne stru
ture Γ and homotopy h. Then we repeatedly eliminate 
ongurations from Φ̂α,Fl [G,Γ, h] when it is safe to do so. Spe
i
ally, we look for a triple φ1, φ2, φ3 ∈ Φ̂α,Fl [G,Γ, h] su
h that reach(φ2) ⊆ reach(φ1) ∪ reach(φ3) and remove φ2 when su
h a triple is found (see Figure 5.1(b)). Although Γ and h play no role in our de
ision to eliminate φ2, they 
ertify that the removal of φ2 is safe. To see this, let L2 be the link from φ2 to G with ne stru
ture Γ and homotopy h (see Figure 5.2(b)). It is safe to remove φ2 if the extension of φ2 by L2 is almost spanned by φ1 or φ2. By our 
hoi
e of φ2, the destination 
onguration of L2 is 
ontained in reach(φ1) or reach(φ3). Suppose the latter (the other 
ase is symmetri
), and let J be the jump from φ3 to the destination 
onguration of L2. If J is free of 
ollisions, then the extension of φ2 by L2 is almost spanned by φ3. To see that J is 
ollision free, noti
e that J is wedged between L2 and L3, where L3 is link from φ3 to 44 FG (a) Links with ne stru
ture C−L0C + from F to G. F G L2 L3 φ3 φ2 J (b) Jump from φ1ℓ to φ 2 ℓ+1 is wedged between L1 and L2. Figure 5.2: We rene our subproblems so that our redundan
y elimination is safe. G with ne stru
ture Γ and homotopy h. This wedging of J between L2 and L3 is true in general: Lemma A.2 states that neither L2 nor L3 
ross J ; moreover, the links L2 and L3 always lie on dierent sides of J by the monotoni
ity of links with stru
ture Γ (see Lemma B.1). This wedging implies that J is 
ollision free be
ause the L2 and L3 have the same homotopy h. Therefore, it is safe to remove φ2 from Φ̂α,Fl [G,Γ, h]. This method of 
onstru
ting Φ̂α,Fl [G,Γ, h] takes time that is polynomially bounded in |Φ̂α,Fl | and n be
ause reach(φ) is easily represented and readily 
omputed: reach(φ) is an interval of orientations (this follows from the arguments in Se
tion A.2); this interval is bounded by links from φ to G be
ause the destination 
onguration of an un
onstrained jump 
an be rolled by a small amount in either dire
tion. Therefore, we 
an lter Φ̂α,Fl in time that is polynomially bounded in |Φ̂α,Fl | and n be
ause there are only O(n) 
hoi
es of G, O(1) 
hoi
es of Γ, and O(n) 
hoi
es for h (see Lemma B.3). In the rest of this 
hapter, we argue that |Φ̂α,Fl [G,Γ, h]| is polynomially bounded in n, m, and l. The stru
ture of this proof is as follows. First, we formalise a property T that Φ̂α,Fl [G,Γ, h] satises. We also argue that Φ̂ α,F l [G,Γ, h] is minimal in this respe
t: no proper subset of Φ̂α,Fl [G,Γ, h] satises T . This minimality implies that the size of Φ̂α,Fl [G,Γ, h] is at most twi
e as large as any set that satises T . Hen
e, it su
es to 
onstru
t a set Ψ that satises T and whose size is polynomially bounded in n, m, and l. We 
on
lude by 
onstru
ting su
h a set and showing that its size is bounded. 5.2.1 Minimality of Greedy Filtering Throughout the remainder of this 
hapter, we assume without loss of generality, by suitable translation and rotation, that F is at the origin and G lies on the positive x-axis. Under this assumption, we 
an represent any 
onta
t 
onguration at G by its 
ounter
lo
kwise angle from the dire
tion of the positive x-axis measured in the range of (−π, π]. We now mention two important properties of reach(φ). Lemma 5.1. Let φ and φ′ be two distin
t 
onta
t 
ongurations. Then 1. reach(φ) is a 
losed subinterval of (−π, π], and 45 2. reach(φ) 6⊆ reach(φ′) and reach(φ) 6⊇ reach(φ′). Proof. The rst property hinges on one fa
t: there is only one 
onguration θ at F that 
an rea
h the 
onguration ψ with the dire
tion π at G (see Figure 5.3). By symmetry, the only 
onguration that θ rea
hes at G is ψ. Re
all that the rea
h reach(φ) is a 
ontiguous range of dire
tions. If φ 6= θ, then reach(φ) does not 
ontain π. In this 
ase, reach(φ) is a subinterval of (−π, π]. Alternatively, if φ = θ, then reach(φ) = [π, π]. GF θ ψ Figure 5.3: Only one 
onguration θ 
an rea
h ψ via a jump from F to G. The se
ond property follows from the fa
t both endpoints of reach(φ) vary mono- toni
ally with φ (see Figure 5.1(b)). This is true be
ause the links bounding the jump spe
trum from φ are monotoni
 in φ (see Lemma B.1). Now we formalise the property that we maintain as we greedily remove 
ongura- tions from Φ̂α,Fl [G,Γ, h]. Let Θ be a set of 
onta
t 
ongurations at F and Reach(Θ) denote ⋃ θ∈Θ reach(θ). Then Reach(Θ) is the set of all 
ongurations at G that 
an be rea
hed via a jump from some 
onguration in Θ. We say that Ψ 
overs Θ, if Reach(Ψ) ⊇ Reach(Θ). We say that Ψ minimally 
overs of Θ, if no proper subset of Ψ also 
overs Θ. We now argue that Φ̂α,Fl [G,Γ, h] minimally 
overs itself. Re
all our 
ondition for removing φ2 from Φ̂α,Fl [G,Γ, h]: we insist that reach(φ 2) ⊆ reach(φ1)∪ reach(φ3), where φ1,φ2, and φ3 are unique 
ongurations of Φ̂α,Fl [G,Γ, h]. We now show that this is equiv- alent to requiring that Φ̂α,Fl [G,Γ, h] \ {φ2} 
overs Φ̂α,Fl [G,Γ, h]: 
learly, if reach(φ2) ⊆ reach(φ1) ∪ reach(φ3), then Φ̂α,Fl [G,Γ, h] \ {φ2} 
overs Φ̂α,Fl [G,Γ, h]; so suppose that Φ̂α,Fl [G,Γ, h] \ {φ2} 
overs Φ̂α,Fl [G,Γ, h]; by Corollary 5.1, reach(φ′) either extends to the left of reach(φ2) or to the right of reach(φ2) but not both, for φ′ ∈ Φ̂α,Fl [G,Γ, h]\{φ2}; let φ1 be the 
onguration of Φ̂α,Fl [G,Γ, h] \ {φ2} su
h that reach(φ1) extends to the left of reach(φ2) and reach(φ1) ∩ reach(φ2) is maximised; similarly, let φ3 be the 
on- guration of Φ̂α,Fl [G,Γ, h] \ {φ2} su
h that reach(φ3) extends to the right of reach(φ2) and reach(φ2)∩reach(φ3) is maximised; then reach(φ2) ⊆ reach(φ1)∪reach(φ3). Hen
e, Φ̂α,Fl [G,Γ, h] minimally 
overs itself, on
e we nish removing redundan
y. We exploit the property that Φ̂α,Fl [G,Γ, h] minimally 
overs itself to bound the size of Φ̂α,Fl [G,Γ, h]. Spe
i
ally, the following lemma implies that |Φ̂α,Fl [G,Γ, h]| is at most twi
e as large as any 
over of Φ̂α,Fl [G,Γ, h]. Lemma 5.2. Let Ψ and Ψ′ be nite 
overs of Θ. If Ψ minimally 
overs Θ, then |Ψ| ≤ 2|Ψ′|. 46 Proof. Let ψ′ be an arbitrary 
onguration in Ψ′. To prove this lemma, we show that there exist ψ1 and ψ2 in Ψ su
h that reach(ψ1) ∪ reach(ψ2) ⊇ reach(ψ′) ∩ Reach(Θ). Hen
e, |Ψ| ≤ 2|Ψ′| by minimality of Ψ. Let ω1 and ω2 be the extreme 
ongurations of reach(ψ) ∩ Reach(Θ). There exists ψ1 ∈ Ψ su
h that ω1 ∈ reach(ψ1) be
ause Reach(Ψ) ⊇ Reach(Θ). So we 
hoose ψ1 su
h that ω1 ∈ reach(ψ1) and reach(ψ1)∩ [ω1, ω2] is maximised. Similarly, we 
hoose ψ2 su
h that ω2 ∈ reach(ψ2) and reach(ψ2) ∩ [ω1, ω2] is maximised. If reach(ψ1) ∪ reach(ψ2) ⊇ reach(ψ′) ∩ Reach(Θ), we are done. So suppose not, and 
onsider ω3 ∈ [reach(ψ′) ∩ Reach(Θ)] \ [reach(ψ1) ∪ reach(ψ2)] for 
ontradi
tion. Then there exists ψ3 ∈ Ψ su
h that ω3 ∈ reach(ψ3) be
ause Reach(Ψ) ⊇ Reach(Θ). Then ω1 6∈ reach(ψ3) be
ause our 
hoi
e of ψ1 maximised reach(ψ1)∩ [ω1, ω2]. Similarly, ω2 6∈ reach(ψ3). Thus, reach(ψ3) ⊂ [ω1, ω2] be
ause ω3 ∈ reach(ψ3)∩[ω1, ω2]. Therefore, reach(ψ3) ⊂ reach(ψ) be
ause [ω1, ω2] ⊆ reach(ψ), whi
h 
ontradi
ts Corollary 5.1. 5.2.2 Generating a Cover By Lemma 5.2, |Φ̂α,Fl [G,Γ, h]| ≤ 2|Ψ|, if Ψ 
overs Φ̂α,Fl [G,Γ, h]. In this se
tion, we des
ribe how to nd su
h a Ψ. We rst dene a sequen
e 〈Ψi〉 that grows: Ψi+1 is the result of adding a 
onstant number of 
ongurations to Ψi. This sequen
e 〈Ψi〉 is 
onstru
ted so that it eventually 
overs Φ̂α,Fl [G,Γ, h]: there exists i su
h that Ψi 
overs Φ̂α,Fl [G,Γ, h]. We 
hoose as Ψ the smallest Ψi that 
overs Φ̂ α,F l [G,Γ, h]. Our goal is to show that |Ψ| is bounded. Our proof that |Ψ| is bounded essentially uses the following reasoning. Suppose that we have an innite sequen
e 〈xi〉 and that we want to show that some xi ex
eeds a 
ertain value b. It is su
ient to show that 〈xi〉 
onverges to a value x∗ and that b < x∗. To bound |Ψ|, we examine the worst 
ase that Ψ must rea
h: let R ⊆ (−π, π] denote the entire range of 
ongurations at G that 
an be rea
hed by any jump from F . We will show that limi→∞Reach(Ψi) = R, in whi
h 
ase we say that 〈Ψi〉 eventually rea
hes R. We also show that Reach(Φ̂α,Fl [G,Γ, h]) ⊂ R. Intuitively, it follows that some Ψi 
overs Φ̂α,Fl [G,Γ, h]. Su
h arguments only show that |Ψ| is nite. To get a better bound on |Ψ|, we quantify the rate at whi
h Reach(Ψi) 
onverges to R and how mu
h smaller Reach(Φ̂α,Fl [G,Γ, h]) is than R. We start by 
hara
terising the set R that Ψ eventually rea
hes. Lemma 5.3. Let ∆ be the distan
e from F to G. If ∆ ≥ 2, then R = (−π, π]. If ∆ < 2, every 
onguration at G that enters one (but not both) of the unit-radius 
ir
les through F and G 
annot be rea
hed by any jump from F to G (see Figure 5.4(
)). Proof. If ∆ ≥ 2, then every 
onguration at G 
an be rea
hed by a jump J from F , where the C-segments of J have the same length and orientation (see Figure 5.4(a)). Suppose that ∆ < 2. The unbounded shaded region in Figure 5.4(b) represents all of the points that 
an rea
h a 
onta
t 
onguration θ at G by a single jump. Hen
e, if one of the two unit radius 
ir
les tangent to 
onguration θ at G 
ontains F , there is 47 no jump from F to θ. Figure 5.4(
) illustrates two ranges of 
ongurations at G that 
annot be rea
hed by a jump from F . Ea
h su
h range is bounded by a 
onguration that has a unit-radius 
ir
le C tangent to it su
h that F lies on the boundary of C. (a) If ∆ ≥ 2, then every 
ongura- tion at G 
an be rea
hed. θ (b) Lo
us of points that 
an rea
h θ via a single jump. GF (
) Some 
ongu- rations 
annot be rea
hed by a jump from F . Figure 5.4: Chara
terisation of the set R of 
ongurations that 
an be rea
hed by a single jump. Corollary 5.4. There are nite neighbourhoods around 
ertain an
hors that belong to R but not Reach(Φ̂α,Fl [G,Γ, h]). Proof. Figure 5.5 shows ve 
ongurations at G that we 
all singularities. We 
all them singularities be
ause ea
h su
h 
onguration 
an only be rea
hed by one 
onguration at F . That ea
h jump is a singularity follows from lo
us arguments similar to the argument illustrated in Figure 5.4(b). For example, 
onsider the singularities that are rea
hed by a single C-segment: to rea
h su
h a singularity from F , we must start on the boundary of the forbidden region in Figure 5.4(b); this implies that a jump to a singularity has a zero-length L-segment be
ause the lo
us of starting points of jumps with non-zero length L-segments does not in
lude the boundary of the forbidden region; similarly, the C-segments of a jump to a singularity must also have the same orientation; hen
e, to rea
h a singularity from a point starting on the boundary, the jump must never leave the boundary. The jumps that rea
h ea
h singularity are symmetri
. Therefore, a 
onguration at F that rea
hes a singularity only rea
hes that singularity. Re
all that the rea
h of one jump spe
trum is 
losed and is never 
ontained in the rea
h of another jump spe
trum (see Corollary 5.1). Hen
e, reach(φ) of a 
onguration φ ∈ Φ̂α,Fl [G,Γ, h] is either a singleton 
ontaining a singularity or an interval that is a nite distan
e away from all singularities. Thus, there are 
ongurations 
lose to ea
h singularity that are not 
ontained in Reach(Φ̂α,Fl [G,Γ, h]). 48 GF Figure 5.5: Ea
h dashed 
onguration at G 
an only be rea
hed by one 
onguration at F via a jump. We now show how to 
onstru
t a 〈Ψi〉 that eventually rea
hes R. We will see that the regions of R that Reach(Ψi) does not rea
h lie in neighbourhoods around singularities. As i grows, these neighbourhoods shrink rapidly. Hen
e, there exists i su
h that Ψi 
overs Φ̂α,Fl [G,Γ, h]. Therefore, |Ψ| is nite. To 
onstru
t 〈Ψi〉, we rst split R into quadrants, where Rq denotes R restri
ted to the qth quadrant (see Figure 5.6(a)). Then we 
onstru
t a 〈Ψqi 〉 that eventually rea
hes Rq. This implies that 〈Ψi〉 eventually rea
hes R, where Ψi = ⋃q Ψqi . We use this approa
h be
ause we 
onstru
t 〈Ψ4i 〉 in su
h a way that ree
tions of 〈Ψ4i 〉 eventually rea
h R1, R2, and R3. First, note that if 〈Ψ4i 〉 eventually rea
hes R4, then the verti
al ip of 〈Ψ4i 〉 eventually rea
hes R1 be
ause if J is a jump from F to R4, then the verti
al ip of J is a jump from F to R1. Similarly, if 〈Ψ2i 〉 eventually rea
hes R2, then the verti
al ip of 〈Ψ2i 〉 eventually rea
hes R3. Therefore, it su
es to 
onstru
t 〈Ψ2i 〉 and 〈Ψ4i 〉. 4 12 3 (a) Range of 
onta
t 
on- gurations at G. J K GF (b) For every jump J with stru
ture C+LC+, there exists a jump K with stru
ture C−LC− su
h that (a) the sour
e 
onguration of J is the reverse of the sour
e 
onguration of K and (b) the destination 
onguration of J is the reverse of the destination 
onguration of K. Figure 5.6: Using symmetries to simplify the 
onstru
tion of 〈Ψi〉. The symmetry that allows us to use a ree
tion of 〈Ψ4i 〉 to 
over R2 is more subtle. Let J be C+LC+-stru
ture jump from F to a 
onguration in R4 (see Figure 5.6(b)). Then there exists a C−LC−-stru
ture jump K from F to R2, where the sour
e 
on- guration of K is the ree
tion through F of the sour
e 
onguration of J and the destination 
onguration of K is the ree
tion through G of the destination 
ongura- 49 tion of J . In our 
onstru
tion of 〈Ψ4i 〉, we ensure that 〈Ψ4i 〉 eventually rea
hes R4 via jumps that have stru
ture C+LC+. Hen
e, the ree
tion of 〈Ψ4i 〉 through F eventually rea
hes R2 via jumps that have stru
ture C−LC−. To 
onstru
t 〈Ψ4i 〉, we take Ψ4i as the rst i 
ongurations of a sequen
e 〈ψj〉 that we dene re
ursively via a fun
tion f : ψj+1 = f(ψj). The sequen
e 〈ψj〉 qui
kly 
onverges to a xed-point ψ∞ of f . This rapid 
onvergen
e is important be
ause the dieren
e between ψi and ψ∞ measures the region of R4 not yet rea
hed by Ψ4i . Of the many 
hoi
es of f available to us, we pi
k one that mimi
s an iterative pro
ess that is known to rapidly 
onverge: the Newton-Raphson method of nding the root of a dierentiable fun
tion g(x). This method works as follows. Let x1 be an estimate of the root of g(x). Then we 
hoose xj+1 as the interse
tion of the line tangent to g(xj) and the x-axis. If 〈xj〉 
onverges to a number x∗, then x∗ is a root of g. Moreover, if x1 is 
hosen 
lose to a root of g(x), then 
onvergen
e of 〈xj〉 to x∗ is very rapid: |xj − x∗| ≤ 22−Ω(j) , for su
iently large j. dj cj cj+1 L T d∞ dj+1 H I (a) Rea
h underestimate. ∆/3 d1 d2 d∞1 (b) Rapid 
onvergen
e of 〈dj〉 to d∞. Figure 5.7: Rea
h underestimate 
onstru
tion (left) and iteration (right). Figure 5.7(a) illustrates our 
hoi
e of f . In this gure, the point dj is the 
entre of a 
lo
kwise-oriented unit-radius 
ir
le tangent to ψj . Given dj, we 
onstru
t dj+1 geometri
ally. Let H be the unit-radius 
ir
le 
entred at F . Let T be the line tangent to H at dj. The dire
tion of T is parallel to the dire
tion of ψj . Let L be the lo
us of points that are equidistant to F and G. The point dj+1 is the horizontal proje
tion onto H of the interse
tion of T and L. The sequen
e 〈di〉 
onverges to a point d∞ where H interse
ts L. This pro
ess 
orresponds to the Newton-Raphson method of nding the interse
tion of H and L. The fun
tion f has the property that the 
ongurations rea
hed by C+LC+-stru
ture jumps from ψj and ψj+1 overlap. Let cj be the ree
tion of dj through L. Then there is a C+LC+-stru
ture jump from the 
ir
le 
entred at dj to any 
ir
le whose 
entre lies on the ar
 between cj and cj+1. To see this, start with the jump J from the 
ir
le 
entred at dj to the 
ir
le 
entred at cj. This is a C +LC+-stru
ture jump where both C-segments have the same length. We 
an deform this jump by rolling J 's destination 
onguration in a 
lo
kwise manner. This 
auses the 
entre of the 
ir
le underlying the se
ond C-segment to move 
lo
kwise along I. It also 
auses the length of the rst C-segment to shrink and the length of the se
ond C-segment to grow. We must stop 50 rolling on
e the length of the rst C-segment be
omes zero. However, at this point the 
entre of the 
ir
le underlying the se
ond C-segment is at the interse
tion of T and I in Figure 5.7(a). Hen
e, there is a C+LC+-stru
ture jump from the 
ir
le 
entred at dj to any 
ir
le whose 
entre lies on the ar
 between cj and cj+1. Figure 5.7(b) shows Reach(Ψ4i ) rapidly approa
hing R 4 . Unfortunately, in order for Reach(Ψ4i ) to 
onverge to R 4 , we would have to begin our iterative pro
ess with d1 set to the point dire
tly below F . Unfortunately, this position is a xed-point of f . To handle this degenera
y, we use the inverse f−1 to dene a sequen
e 〈ψ−i〉 where ψ−(i+1) = f−1(ψ−i) (see Figure 5.8(a)). Let Ψ4i = {ψ−i, ψ−i+1, . . . , ψ−1, ψ1, ψ2, . . . , ψi}. By a 
areful 
hoi
e of d1 and d−1 in terms of the distan
e ∆ between F and G (see Figures 5.7(b) and 5.8(a)) guarantees that Reach(Ψ4i ) is 
ontiguous (see Figure 5.8(b) and Lemma C.2). Moreover, Reach(Ψ4i ) rapidly 
onverges to all of R. d−2d−∞ d−1 ∆/5 (a) Rapid ba
kward 
onvergen
e. d1 d −1 (b) Rea
h underestimates overlap. Figure 5.8: Ba
kwards iteration (left) 
ombined with a suitable starting point (right). In Appendix C, we expli
itly bound the rate of 
onvergen
e of Reach(Ψ4i ) to R 4 . We formalise this by measuring how far dj and d−j are from their respe
tive xed points d∞ and d−∞. Let ξ+ (j) denote the verti
al distan
e between d+j and d+∞. Similarly, let ξ− (j) denote the verti
al distan
e between d−j and d−∞. Theorem 5.5. The distan
e ξ±(j) ≤ 2−Ω(j), for j ≥ 1. If the distan
e between F and G is not exa
tly two, then ξ±(j) ≤ 2−2Ω(j) , for j > O(m). Proof. See Appendix C. 5.2.3 Separation Bound The previous theorem bounds just how rapidly 〈Ψi〉 rea
hes R. In this se
tion, we bound the rea
h of Φ̂α,Fl [G,Γ, h] away from R. These two bounds will imply that |Ψ| is polynomially bounded, where Ψ is the smallest Ψi that 
overs Φ̂ α,F l [G,Γ, h]. In turn, this implies that Φ̂α,Fl [G,Γ, h] is polynomially bounded by Lemma 5.2. To bound the rea
h of Φ̂α,Fl [G,Γ, h] away from R, we use a result of Burnikel et al. [11℄: given an expression E 
omposed of integer operands and arithmeti
 operators (+, −, ×, /, and √ ), they bound how dierent the value of E must be from zero, if 51 the value of E is not exa
tly zero. This separation bound is 
al
ulated dire
tly from the arithmeti
 expression. Theorem 5.6. [11℄Let E be an expression with integer operands and operations +, −, ×, /, and √ . Let ξ be the value of E, let s be the number of square-roots in E, and let u (E) and l (E) be dened re
ursively on the stru
ture of E by the rules shown in the table below. Then ξ = 0 or |ξ| ≥ ( l (E)u (E)2 s−1)−1 . u (E) l (E) integer N |N | 1 E1 ± E2 u (E1) l (E2) + l (E1)u (E2) l (E1) l (E2) E1 × E2 u (E1)u (E2) l (E1) l (E2) E1/E2 u (E1) l (E2) l (E1)u (E2)√ E1 √ u (E1) √ l (E1) The above theorem denes the separation bound ξ of an expression E in terms of the entire stru
ture of E. For our purposes, we do not need the full generality of this theorem. We are satised with the following 
orollary that denes the separation bound ξ in terms of the number of operators in E. Corollary 5.7. Let E be an expression 
omposed of integer operands of magnitude at most 2m and e arithmeti
 operations (either +, −, ×, /, or √ ). Let ξ be the value of E. Then either ξ = 0 or |ξ| ≥ 2−m6e. Proof. LetM (E) = max {u (E) , l (E)}. We now argue thatM (E) ≤ 2m·3eby indu
tion on e. The base 
ase is e = 0, where E is an integer of magnitude at most 2m. Then M (E) ≤ 2m = 2m·3e . So suppose that M (F ) ≤ 2m·3f and M (G) ≤ 2m·3g , for expressions F and G with f < e and g < e operations respe
tively. We now 
onsider the various 
ases that 
ould possibly generate E. Suppose that E = √ F . Then M (E) = √ M (F ) ≤ √ 2m·3f ≤ 2m·3f ≤ 2m·3e by our indu
tive hypothesis. Suppose that E = F ± G. Then u (E) = u (F ) l (G) + l (F ) u (G) ≤ 2 ·M (F ) · M (G) ≤ 2 · 2m·3f · 2m·3g = 2m(3f+3g)+1 ≤ 2m(3f+3g+1), by our indu
tive hypothesis. Now, e = f + g + 1, so our desired bound is a
hieved if 3f + 3g + 1 ≤ 3f+g+1. This inequality is true if and only if 3−g−1 + 3−g−1 + 3−f−g−1 ≤ 1. Ea
h ea
h term on the left side is 
learly less than 1 3 . Hen
e, u (E) ≤ 2m·3e . From the denition l (E) = l (F ) · l (G) ≤ M (F ) ·M (G) ≤ 2m·3f · 2m·3g = 2m(3f+3g) < 2m(3f+3g+1) ≤ 2m·3e , by our indu
tive hypothesis. The reasoning for E = F × G and E = F/G are similar (and simpler) than the previous 
ase. Therefore, M (E) ≤ 2m·3e in general. 52 Clearly the number of square roots in E is less than e. So the previous theorem implies that either ξ = 0 or |ξ| ≥ ( l (E)u (E)2 e−1)−1 ≥M (E)−2e ≥ (2m·3e)−2e = 2−m·6 e . In Corollary 5.4, we argued that there are regions of R around singularities are not part of Reach(Φ̂α,Fl [G,Γ, h]). We now derive an expression for the 
onguration φ′ ∈ Reach(Φ̂α,Fl [G,Γ, h]) that gets as 
lose as possible to a singularity α′. Combined with the above 
orollary, this will give us a bound on how dierent Reach(Φ̂α,Fl [G,Γ, h]) is from R. In the dis
ussion that follows, we use a natural representation for 
onta
t 
ongurations: at a wall, we use the point where the 
onguration tou
hes the wall; at a 
orner, we use a unit-length ve
tor in the dire
tion of the 
onguration. Lemma 5.8. Let α′ be an an
hor at G and φ ∈ Φ̂α,Fl [G,Γ, h]. If φ′ is the 
onguration in the rea
h of φ that is 
losest to α′, then either φ′ = α′ or φ′ 
an be expressed with integers operands of magnitude at most 2m and O(l) operators. Proof. Let φ′ be the 
onguration at G in the rea
h of φ that is 
losest to α′. If φ′ = α′, then we have nothing to prove. Otherwise, φ rea
hes φ′ via a link be
ause the jump spe
trum from φ to G is bounded by links. Although, we are not sure whi
h link from φ leads to φ′, there are only O(1) su
h links, so we 
an try them all. The existen
e of a link from φ to φ′ means that φ′ 
an be 
al
ulated from α with O(l) arithmeti
 operations. Re
all, that φ ∈ Φ̂α,Fl [G,Γ, h] implies that there is a l-link 
hain from α to φ. Hen
e, there is a (l+1)-link 
hain from α to φ′. Also re
all that the nal 
onguration of a link is a fun
tion of its sour
e 
onguration. Therefore, φ′ 
an be 
al
ulated from α by evaluating (l + 1) link fun
tions. Finally, ea
h link fun
tion 
an be expressed with O(1) arithmeti
 operators and integer operands with magnitude at most 2m (ea
h 
orner 
oordinate is the ratio of two su
h integers). Therefore φ′ 
an be 
al
ulated from α with O(l) arithmeti
 operations. An
hors are the 
ongurations on over-
onstrained links. Hen
e, α 
an be expressed with O(1) arithmeti
 operators and O (1) 
orner 
oordinates. Hen
e, φ′ 
an be 
al
u- lated with O(l) arithmeti
 operators. This separation bound and Theorem 5.5 have an immediate impli
ation. Corollary 5.9. The size of Φ̂α,Fl [G,Γ, h] is at most O(m+ l). Proof. Let φ′ be the 
onguration in Reach(Φ̂α,Fl [G,Γ, h]) that gets as 
lose to a singu- larity α′ as possible without rea
hing it. Then φ′ 
an be expressed with integer operands of magnitude at most 2m and O(l) operators by Lemma 5.8. With an additional O(1) operators, we 
an transform φ′ into the 
oordinate system where we did our analysis of how qui
kly 〈Ψi〉 rea
hes R. In this frame of referen
e, we 
an express the verti
al distan
e between φ′ and α′ with O(l) operators. By Corollary 5.7, this distan
e must be 2−m2 O(l) . We only argue the 
ase where the distan
e ∆ from F to G is not exa
tly 2. In this 
ase, we 
an apply Theorem 5.5. This theorem implies that the set Ψi rea
hes all 53 of R, ex
ept a small amount with verti
al distan
e of 2−2 Ω(i) from the singularities, for i > O(m). Therefore, Ψi 
overs Φ̂ α,F l [G,Γ, h] for some i ∈ O(m)+(l+logm) = O(l+m). Hen
e, |Ψ| ∈ O(l + m). Re
all that |Φ̂α,Fl [G,Γ, h]| ≤ 2|Ψ| by Lemma 5.2. Thus, |Φ̂α,Fl [G,Γ, h]| ∈ O(l +m). When the distan
e ∆ from F to G is exa
tly 2, we 
an a
hieve a polynomial bound with a more detailed analysis that exploits symmetry further. 5.3 Bounds on the Run Time In this se
tion we derive a loose bound on the run time of path nding algorithm. Re
all that rst we 
onstru
t an an
hor graph, and then we look for a shortest path in the an
hor graph. The rst phase is the most 
omputationally expensive. It is 
arried out by the algorithm AllViableLinkages (see Figure 4.4). Its run time depends on the number of 
hains that are generated. This in turn depends on the ee
tiveness of ltering. In Corollary 5.9, we state an expli
it bound on the ee
tiveness of one important step of ltering. We now use this to get an expli
it bound on |Φ̂α,Fl |. Lemma 5.10. Before ltering, the size of Φ̂α,Fl is at most O(n 6(m+ l)). Proof. We rst bound the size of Φ̂α,Fl after it has been ltered. If F is a wall, then Φ̂ α,F l 
ontains at most two 
hains after ltering. Otherwise, we partition all of the possible one link extensions of Φ̂α,Fl a

ording to the feature G that is rea
hed by the link, the ne stru
ture Γ of the link, and the homotopy h of the link. For ea
h of the O(n) 
hoi
es of G, O(1) 
hoi
es of Γ, and O(n) 
hoi
es of h, we identify a subset Φ̂α,Fl [G,Γ, h] of Φ̂α,Fl so that every one link extension of Φ̂ α,F l to G with stru
ture Γ and homotopy h is almost spanned by a 
hain in Φ̂α,Fl [G,Γ, h]. Clearly, ⋃ G,Γ,h Φ̂ α,F l [G,Γ, h] satises the 
ompleteness property with respe
t to Φ̂α,Fl . By Corollary 5.9, ⋃ G,Γ,h Φ̂ α,F l [G,Γ, h] 
ontains at most O(n2(m+ l)). To get a bound on |Φ̂α,Fl | before it is ltered, we work ba
kwards: ea
h 
hain in Φ̂α,Fl is a one link extension of a 
hain in Φ̂ α,G l−l , for some G; there are O(n) 
hoi
es of G and O(1) possible ne stru
tures for the one link extension, so |Φ̂α,Fl | is at most O (∑ G |Φ̂α,Gl−l | ) ⊆ O(n × maxG |Φ̂α,Gl−1 |). Every 
hain φ in Φ̂α,Fl has a prex φ′ that was ltered. If φ′ is the longest su
h prex of φ, then φ is at most four links longer than φ′. It follows that |Φ̂α,Fl | is at most O(n6(m+ l)). The time spent propagating 
hains depends on the number of 
hains generated. There are O(n3) an
hors and we only generate 
hains with at most O(nk) links. Hen
e the number of 
hains generated is at mostO(n10k(m+nk)). Ea
h 
hain that is generated must be tested for feasibility. Fortunately, it su
es to 
he
k the last link be
ause all of the other links must have been feasible in order for the 
hain to be generated. Ea
h link 
onsists of at most three segments and ea
h segment 
an be tested for feasibility in O(n) time. Hen
e, the total time spent propagating 
hains is at most O(n12k(m+nk)). 54 We now bound the time spent ltering 
hains. Re
all that in the worst 
ase, the 
all to Filter identies O(n2) subproblems. As des
ribed earlier in Se
tion 5.2, the time spent sele
ting Φ̂α,Fl [G,Γ, h] is 
ubi
 in the size of |Φ̂α,Fl | . Hen
e, ea
h 
all to Filter takes O(n20(m+ nk)3) time. There are O(n3) dierent an
hors and we 
onsider 
hains with O(nk) links, so Filter is 
alled O(n4k) times. Therefore, the total time spent ltering is O(n24k(m+ nk)3). It remains to bound the times that it takes to join one 
hain to another. In the worst 
ase we try to join every 
hain to every other 
hain. There are at mostO(n20k2(m+nk)2) su
h pairs. For ea
h pair, we try to join them with at most eight links and one jump. There are O(n8) su
h paths. It takes O(n) time to test the feasibility of ea
h su
h path be
ause ea
h su
h path has at most 27 segments. Therefore, AllViablePaths takes at most O(n29k2(m+ nk)2) +O(n24k(m+ nk)3) ⊂ O(n29k2(m+ nk)3) time. 55 Chapter 6 Shortest Bounded-Curvature Path Approximation As dis
ussed in Se
tion 2.2.1, nding a shortest bounded-
urvature path amid arbitrary polygonal obsta
les is NP-hard [23℄, even if the length and intri
a
y of a shortest path are known to be linear in n and m. Previous work on approximation algorithms has provided a (1 + ε)-approximation to the shortest ε-robust bounded-
urvature path [18, 3℄. Although these results are very e
ient (O(n2ε−4 log n) in [3℄), the restri
tion to ε- robust paths is non-negligible. Spe
i
ally, robust solutions do not exist for all problem instan
es that admit bounded-
urvature paths. Furthermore, even if a ε-robust path exists, the shortest bounded-
urvature path may be arbitrarily shorter than the shortest ε-robust path. Finally, these approa
hes do not really address the di
ulty exposed by the NP-hardness result be
ause the only feasible paths in the asso
iated redu
tion have very low robustness (2−Ω(n)); in other words, it is 
ompletely 
onsistent with existing approximation algorithms that no general polynomial-time approximation s
heme exists for shortest bounded-
urvature paths. In this 
hapter, we des
ribe an algorithm that unies and extends previous work on the feasibility and approximation of bounded-
urvature paths. Spe
i
ally, our new algorithm removes the robustness requirement: it returns a (1+ε) approximation to the shortest path, whereas previous results return a (1 + ε) approximation to the shortest ε-robust path. A measure of length is taken as input by our algorithm. This measure is made relative to 
urvature bound. Spe
i
ally, we assume without loss of generality that the environment is s
aled so that the 
urvature bound is one unit. Given a length parameter λ, our algorithm either (i) veries that every feasible path has length greater than λ or (ii) returns a feasible path that is at most (1 + O(ε)) times longer than the shortest feasible path. The run time of the algorithm is polynomially bounded in n, m, ε−1, and λ. (It follows, of 
ourse, that we 
ould produ
e a true (1 + ε) approximation by s
aling ε appropriately. In fa
t, we will assume that our ε satises ε−1 ≥ γn2λ, for some 
onstant γ > 0.) Compared with our previous result, this new result ex
hanges a polynomial dependen
e on k (the minimum path intri
a
y) for a polynomial dependen
e on the minimum path length λ. The intuition behind this swit
h is straightforward: in 56 pra
ti
e, the desired approximation Π 
an be found in time dependent on its intri
a
y; however, to 
ertify that Π is 
lose to optimal, we look for paths that are shorter than Π; in general, a shorter path may have mu
h greater intri
a
y than the intri
a
y of Π; fortunately, we 
an bound the intri
a
y of any path that is shorter than Π in terms of n and ‖Π‖; hen
e, we 
an phrase our runtime bound in terms of λ instead of k. In the remainder of this 
hapter, we rst des
ribe a path normalisation pro
edure that in
orporates the 
riti
al observations from the previous approximation results [18, 3℄ with the te
hniques developed in Chapter 3. After normalising a shortest path, the resulting path is at most (1 + ε) times longer and has a 
ombinatorial des
ription. This allows us to nd an approximately shortest path by enumerating a nite (but potentially exponential-size) spa
e. We next des
ribe the redundan
y used to lter the enumeration, whi
h results in an e
ient algorithm. This redundan
y is a renement of the redundan
y that we exploited in Chapter 4. This redundan
y allows us to asso
iate a su

in
t set of 
ongurations with every environment feature. These 
ongurations serve as an adequate set of potential 
he
kpoints in the 
onstru
tion of a path. The total size of these 
onguration sets is a dominant fa
tor in the 
omplexity of our algorithm. Thus, the 
riti
al step in our analysis is the demonstration that we 
an maintain a polynomial bound on the size of these 
onguration sets while still a
hieving a good approximation. The te
hniques used to maintain su
h a bound are extensions of those developed in Chapters 4 and 5. 6.1 Path Normalisation In Chapter 2, we surveyed prior algorithmi
 results in bounded-
urvature motion plan- ning that either normalise a given feasible path [17, 8, 5℄ or 
hara
terise shortest feasible paths [2, 1, 10, 3, 18℄. The stru
ture that results from normalisation enables a system- ati
 sear
h for a path and narrows the spa
e of paths 
onsidered. In this se
tion, we 
ombine our new normalisation approa
h (see Chapter 3) with the approa
h taken by the previous approximation algorithms [18, 3℄. The intuition behind this hybrid is straightforward. Re
all that our normalisation deforms a path until ea
h 
onta
t 
on- guration is moored. Spe
i
ally, if 
onta
t 
onguration ever be
omes an an
hor, it will remain un
hanged. To limit how mu
h a path is deformed by normalisation, we introdu
e new an
hors. The result is that a path is stret
hed by at most a fa
tor of (1 + ε) by normalisation. In Se
tion 2.1, one of the results that we dis
ussed is the following 
hara
terisation of shortest bounded-
urvature paths in free spa
e. Theorem. [16℄ In the absen
e of obsta
les, a shortest bounded-
urvature path is type CLC or CCC. If its stru
ture has type CCC, the middle C-segment has length at least π. We 
all a bounded-
urvature path with the properties set out in the above theorem a Dubins jump. A Dubins jump diers from our earlier notion of a jump in that it may 57 have C-segments with length greater than π and may have stru
ture CCC. In this 
hapter, the only types of jumps that we will 
onsider are Dubins jumps. Dubins jumps play an important role in this 
hapter be
ause amid arbitrary polygonal obsta
les, any shortest bounded-
urvature path 
an be expressed as a sequen
e of Dubins jumps (as rst noted in Se
tion 2.2.4). Corollary. [18℄ Let Π be any shortest bounded-
urvature path amid polygonal obsta
les. When we split Π at its 
onta
t 
ongurations, ea
h resulting 
onta
t-free subpath is a Dubins jump. We 
all any path that satises the above property JC-normal. This normal form is a generalisation of the FW-normal form. We 
an represent a JC-normal path in the same way that we represent a FW-normal path: as a sequen
e of 
onta
t 
ongurations 〈θi〉 and a sequen
e of strings 〈Γi〉, where Γi is the stru
ture of the jump from θi to θi+1. This representation redu
es the problem of nding paths to that of determining whi
h 
onta
t 
ongurations 
an be rea
hed from a given start 
onguration. Figure 6.1 represents a 
ontinuous range of JC-normal paths from the same start 
onguration to the same terminal 
onguration. Noti
e that there is a 
ontinuous range of 
onta
t 
ongurations, but in ea
h 
ase, only one 
onguration represents a path of minimal length. Finding a shortest path requires identifying this single 
onguration, but (as we shall see) approximating it only requires nding a nearby 
onguration. αs αt (a) Conta
t 
onguration 
an pivot about a 
orner. αt αs (b) Conta
t 
onguration 
an slide along a wall. Figure 6.1: Conta
t 
onguration degree of freedom. To this point, optimality has restri
ted our attention to a 
ontinuous spa
e of JC- normal paths. As we des
ribe in Chapter 3, to further restri
t our attention to a 
ountable set of paths, we impose additional 
onstraints: we roll 
onta
t 
ongurations while keeping ea
h su
h 
onguration θi in 
onta
t with every feature that it tou
hes. Even with this restri
tion, θi may still have one degree of freedom: when θi 
onta
ts a single 
orner, the position of θi is xed, but its orientation may vary (see Figure 6.1(a)); when θi 
onta
ts the interior of a wall, the dire
tion of θi is xed, but its position may vary (see Figure 6.1(b)). These 
onta
t-preserving motions (pivoting and sliding, respe
tively) are the only ways that we deform paths. When we pivot, the rolling distan
e is measured in radians; when we slide, the rolling distan
e is measured in standard distan
e units. Using this notion of rolling, we 
an formalise the denition of ε-robustness that is 
entral to previous approximation results (rst dened in Se
tion 2.2.4). A jump 58 between two 
onta
t 
ongurations is ε-robust if every simultaneous and independent ε- perturbation of its endpoint 
ongurations 
an be joined by another feasible jump of the same stru
ture. More generally, a JC-normal path is ε-robust if ea
h if its 
onstituent jumps is ε-robust. Note that a jump is non-robust if, for some ε-perturbation of ea
h of its endpoint 
ongurations either (i) the resulting 
onguration pair 
annot be joined by a jump without violating feasibility, or (ii) the resulting 
onguration pair 
an be joined by a feasible jump but only by undergoing a stru
tural 
hange. It follows from 
ondition (ii) that ea
h segment of an ε-robust jump must be non-degenerate. The next lemma makes pre
ise the intuition that small deformations of a jump J result in at most a small in
rease its length ‖J‖. Lemma 6.1. [3℄ Let J and J ′ be any pair of similar-stru
ture jumps between the same two features. Then |‖J ′‖ − ‖J‖| is bounded by the sum of the distan
es between the 
orresponding endpoints of J and J ′. If a jump J between two 
onta
t 
ongurations is ε-robust, ‖J‖ must be at least ε. It follows from the lemma above that if we perturb the sour
e and destination 
ongurations of J by at most O(ε2), the length of the result is at most ‖J‖ + ε2 ≤ (1 + ε)‖J‖. Therefore, simultaneously and arbitrarily perturbing ea
h 
onta
t on an ε-robust path Π by O(ε2) 
auses the length of Π to in
rease by a fa
tor of at most (1 + ε). The previous algorithms that nd a (1 + ε) approximation to the shortest ε-robust path 
an be des
ribed as follows [18, 3℄: (i) sample the spa
e of possible 
onta
t 
ongu- rations with O(ε2) granularity, and (ii) nd the shortest JC-normal path Π where ea
h 
onta
t 
onguration is a sampled 
onguration. The 
hoi
e of O(ε2) granularity is used to 
onvert the absolute error bound given in Lemma 6.1 to a relative error bound. Spe
i
ally, to see that Π exists and is a (1 + ε) approximation, let Π′ be the shortest ε-robust path. We 
an perturb ea
h 
onta
t 
onguration of Π′ by at most O(ε2) to get Π′′ su
h that ea
h 
onta
t 
onguration of Π′′ is a sampled 
onguration. Then Π′′ is a (1 + ε) approximation of Π′ by Lemma 6.1. Therefore, Π is at most (1 + ε) times longer than Π′ be
ause Π is no longer than Π′′ by our 
hoi
e of Π. We now des
ribe a new type of normalisation that 
opes with the degenera
ies that prevent a JC-normal path Π from being ε-robust. The general approa
h is the same as we used in Chapter 3. However, it is 
ompli
ated by that fa
t that, in order to 
onsider only approximately-shortest paths, we must now deal with a family of paths whose form is less restri
tive. As with the previous approximation approa
hes, we rst uniformly sample the spa
e of possible 
onta
t 
ongurations, at ea
h of the O(n) obsta
le features, with granularity O(ε2). In addition, we identify, for ea
h obsta
le feature, the O(n3) 
onta
t 
ongurations that o

ur on over-
onstrained jumps (the type 1, 2, and 3 an
hor 
ongurations dened in Chapter 3). Together, we refer to these sampled 
ongurations, over-
onstrained 
ongurations, start 
onguration αs, and terminal 
onguration αt, as an
hor 
ongurations. There are O(n 3 + nε−2) su
h 
ongurations in total. 59 Next, we 
ontinuously deform Π while preserving all of its 
onta
ts and segment degenera
ies. The goal is to exer
ise any residual degrees of freedom in the path to bring its 
onta
t 
ongurations as 
lose as possible to an an
hor 
onguration. Our approa
h is the same as in Chapter 3. If some 
onta
t 
onguration 
annot be rolled dire
tly to an an
hor 
onguration, we are able to introdu
e a new 
onstraint. Eventually, the path be
omes 
ompletely 
onstrained and there is no freedom left. We summarise our new normalisation result in the following theorem. Theorem 6.2. Let Π be an arbitrary bounded-
urvature path of length ‖Π‖ from a 
onguration αs to a 
onguration αt. Then there exists an ε-dis
rete path Π ′ from αs to αt with length at most ‖Π‖(1+O(nε2)) and O(n‖Π‖) non-an
hor 
onta
t 
ongurations. Proof. We rst observe that the shortest feasible bounded-
urvature path Π from αs to αt has O(n‖Π‖) 
onta
t 
ongurations. The intuition behind this 
laim is that the shortest bounded-
urvature path from a feature to the same feature is a unit radius 
ir
le. Hen
e, if we split Π into subpaths of length 2π, ea
h subpath tou
hes ea
h of the n features at most on
e. This reasoning is pre
ise for 
orners, but we must rene it for walls. Noti
e that on
e Π rea
hes a wall w at a 
onguration θ, Π 
an follow w to rea
h other 
onta
t 
ongurations at w in the dire
tion of θ. Hen
e, on
e Π leaves w after θ, it must loop ba
k (travel at least 2π) before rea
hing w in the dire
tion of θ be
ause otherwise (as a shortest path) Π should not have left w. This implies that ea
h subpath of length at most 2π has O(1) 
onta
t 
ongurations at any parti
ular wall. The proof that we 
an normalise Π to get a ε-dis
rete path Π′ follows from the proof of Theorem 3.7: intuitively, we 
an roll unmoored 
ongurations of Π until there are no unmoored 
ongurations left. The analysis in Theorem 3.7 indi
ates that this pro
ess 
auses at most a 
onstant fa
tor in
rease in the number of non-an
hor 
onta
t 
ongurations. Hen
e, Π′ has at most O(n ‖Π‖) non-an
hor 
onta
t 
ongurations be
ause Π has at most O(n ‖Π‖) 
onta
t 
ongurations. It remains to argue that Π′ is at most (1 + O(nε2)) times longer than Π. This fa
t hinges on three invariants of rolling a 
onguration: it preserves the Π's 
onta
t with the environment (
onta
t 
ongurations may 
hange, but the 
onta
t persists); it preserves the stru
ture of the path between any two 
onta
ts (spe
i
ally, stru
tures only be
ome more 
onstrained); and it limits the net 
hange in any 
onta
t 
onguration to at most ε2 (this follows from our 
hoi
e of an
hors). It follows from Lemma 6.1 that ea
h jump between 
onse
utive 
onta
ts of Π is stret
hed by at most ε2. We argued above that there are O(n‖Π‖) su
h jumps. Therefore, ‖Π′‖ ≤ ‖Π‖ + O(ε2n‖Π‖) = (1 +O(nε2))‖Π‖. An important property of all ε-dis
rete paths is that they admit a 
ombinatorial des
ription: ea
h su
h path 
onsists of a sequen
e of 
onta
t 
ongurations ea
h of whi
h is either an an
hor 
onguration or is rea
hable from an an
hor 
onguration by a sequen
e of links. 60 6.2 Systemati
 Sear
h for Shortest ε-Dis
rete Paths In this se
tion, we des
ribe an algorithm that 
onstru
ts a feasible path Π′ that is at most (1+ ε) times longer than the shortest feasible path Π, provided that Π has length at most λ. Using the assumption stated in the introdu
tion of this 
hapter that ε is su
iently small, there exists an ε-dis
rete path Π′ with length at most (1+ε) ‖Π‖ and at most O(nλ) 
onta
t 
ongurations by Theorem 6.2. We 
an systemati
ally sear
h for this path be
ause ε-dis
rete paths have a 
ombinatorial des
ription. Our approa
h is roughly the same as the approa
h in Chapter 4. We 
onstru
t an an
hor graph and nd the shortest path P in the an
hor graph. This path P 
orresponds to a feasible bounded-
urvature path Π′ that is at most (1 + ε) times longer that the shortest feasible path. There is one important dieren
e between the an
hor graph 
onstru
ted in Chapter 4 and the an
hor graph that we now 
onstru
t: the weight of an edge now 
orresponds to the length of a linkage, rather than the number of 
onta
t 
ongurations on a linkage. Sin
e we are looking for an ε-dis
rete path with at most O(nλ) 
onta
t 
ongurations, it su
es to nd a shortest (α, α′)-linkage with at most O(nλ) 
onta
t 
ongurations, for every pair of an
hor 
ongurations α, α′. Figure 6.2 outlines a systemati
 way to nd the shortest (α, α′)-linkage that has most τ 
onta
t 
ongurations, for every pair of an
hor 
ongurations α, α′. This algorithm is very similar to the exhaustive algorithm introdu
ed in Chapter 4 (see Figure 4.2). This new algorithm keeps tra
k of the shortest (α, α′)-linkage, whereas the previous algorithm keeps tra
k of the (α, α′)-linkage with the least number of 
onta
t 
ongurations. AllLinkages(τ) 1 for all an
hor 
ongurations α do for h = 1 to τ do for all environment features F do Propagate(Φα,Fl−1 ) 2 for all pairs of an
hor 
ongurations α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su
h that l + l′ ≤ τ do determine if there exist 
ongurations φ in Φα,Fl and φ′ in Φα ′,F ′ l′ su
h that: (i) the jump joining φ and φ′ is 
ollision-free, and (ii) the (α, α′)-linkage through φ and φ′ is shorter than the shortest (α, α′)-linkage found so far. Figure 6.2: Pro
edure for the 
onstru
tion of all shortest (α, α′)-linkages with τ 
onta
t 
ongurations. The algorithm in Figure 6.2 suers from the same problem as the algorithm in Figure 4.2: the size of Φα,Fl 
ould be exponential in l. Fortunately, it su
es to dis
over 61 only a single (α, α′)-linkage that is approximately the same length as the shortest (α, α′)-linkage. This allows us to identify and propagate only a subset of rea
hable 
ongurations at ea
h feature in ea
h propagation phase. As before, the intuition is that if two rea
hable 
ongurations at a feature F are su
iently similar then it should be possible to repla
e one by the other in all paths that use the rst without sa
ri
ing feasibility or signi
antly in
reasing the length of the path. While this intuition is basi
ally 
orre
t, the details of what 
onstitutes su
iently similar and the analysis of the impa
t of this redundan
y elimination are somewhat involved. 6.3 Redundan
y Among Conta
t Congurations By allowing a fa
tor (1 + ε) in
rease in length, we were able to restri
t our sear
h to a nite spa
e of paths (for a xed λ). In this se
tion, we use a further potential in
rease in length to restri
t our sear
h to a spa
e of paths that is polynomially bounded in size. In this se
tion, we argue that it su
es to 
al
ulate a subset Φ̂α,Fl of Φ α,F l , if we allow a slight in
rease in path length. We start by rening the notion of almost spanning dened in Se
tion 4.2. Re
all that we said that a 
hain φ′ almost spans a 
hain φ, if two 
onditions are satised (see Figure 4.3): (a) φ′ and φ begin at the same 
onguration and (b) we 
an append φ′ with at most one jump J and at most one link K to rea
h the nal 
onguration of φ. In the 
ontext of approximation, we add a third 
ondition to the notion of almost spanning: (
) ‖φ′‖+ ‖J‖+ ‖K‖ ≤ ‖φ‖+ 2ε2. When nding 
hains that start with a parti
ular an
hor, we want to avoid produ
ing redundant 
hains. We do this with a pro
edure Filter, whi
h we 
all periodi
ally to remove 
hains that we do not need to extend (see Figure 6.3). The important aspe
t of of ltering is that is does not eliminate too many 
hains, whi
h we formalise with the Completeness Property below. The 
ondition distinguishes between the 
hains that Filter removes (unviable 
hains) and those that are not removed (viable 
hains). Completeness Property: If a 
hain φl ∈ Φ̂α,Fl is unviable, then ea
h one-link exten- sion φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . In Chapter 5, we dis
ussed how to implement Filter when the notion of almost span- ning just required 
onditions (a) and (b) above. The approa
h was a divide-and-
onquer algorithm: it divided Φ̂α,Fl into subproblems where it was easy to satisfy the Complete- ness Property. To satisfy 
ondition (
), we make the subproblems smaller. We begin by partitioning Φ̂α,Fl into subsets Φ̂ α,F l [i] su
h that the lengths of the 
hains in Φ̂ α,F l [i] lie in the range [(i − 1)ε2, iε2). Sin
e we restri
t our attention to paths of length at most λ(1 + O(ε)), the number of resulting partitions is at most λ(1 + O(ε))/ε2. We then lter ea
h of these partitions in almost the same way as des
ribed in Chapter 5. The main dieren
e is that if L is the link from φl to φl+1 in the Completeness Property, we are 
areful that the length ‖J‖+ ‖K‖ of the path that extends φ′l to rea
h φl+1 ex
eeds ‖L‖ by at most ε2. Hen
e, 
ondition (
) of the denition of almost spanned is satised: ‖φ′l‖+ ‖J‖+ ‖K‖ ≤ [‖φl‖+ ε2] + [‖L‖+ ε2] = ‖φl+1‖+ 2ε2. 62 AllViableLinkages(τ) 1 initialise Φ̂α,F0 for all α and F for all an
hors α do for h = 0 to τ − 1 do for all environment features F do if (h is divisible by 4) then Φ̂α,Fl ← Filter(Φ̂α,Fl ) Propagate(Φ̂α,Fl ) 2 for all pairs of an
hors α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su
h that l + l′ ≤ τ do determine if there exist φ ∈ Φ̂α,Fl and ψ ∈ Ψ̂α ′,F ′ l′ su
h that: (i) there is a path Π from φ to ψ with at most 8 links and one jump, and (ii) φ+Π + ψ is shorter than any (α, α′)-linkage found so far. Figure 6.3: Pro
edure for the 
onstru
tion of all shortest viable (α, α′)-linkages with τ non-an
hor 
onta
t 
ongurations. The result of repla
ing a unviable 
hain with a viable 
hain may not be ε-dis
rete. The next lemma shows that an unviable 
hain is also redundant when we restri
t our attention to ε-dis
rete paths. It is a slight extension of Lemma 4.2. This next result is used in main result of this 
hapter. Lemma 6.3. Let φl+1 be a one link extension of an unviable φl ∈ Φ̂α,Fl . If φl+1 is the prex of some (α, α′)-linkage Λ with O(nλ) non-an
hor 
onta
t 
ongurations, there exists a ε-dis
rete path P from α to α′ su
h that 1. a viable 
hain φ′l ∈ Φ̂α,Fl is the prex of P , 2. the sux of Λ is a sux of P , 3. P has at most three more non-an
hor 
onta
t 
ongurations than Π, and 4. ‖P‖ ≤ ‖Π‖+O(ε2nλ). Proof. To 
onstru
t P , we start with Λ and repla
e φl+1 with some φ ′ l that almost spans it. By our denition of almost spanned, the resulting path Λ′ is at most 2ε2 units longer than Λ and has at most one more 
onta
t 
onguration than Λ. This path Λ′ is JC-normal but not ne
essarily ε-dis
rete. So we normalise Λ′. This results in a length in
rease of at most O(ε2nλ) be
ause Λ′ has O(nλ) jumps that are deformed by 63 normalisation (only the non-an
hor 
onta
t 
ongurations 
an 
hange). This explains 
ondition 4. Conditions 1 through 3 follow from the proof of Lemma 4.2. With the pre
ise notion of redundan
y given in the previous lemma, we now prove that AllViableLinkages 
an be used to nd a feasible path. Theorem 6.4. Suppose that there exists a bounded-
urvature path Π from a start 
on- guration αs to a terminal 
onguration αt with length at most λ. Then there is an ε-dis
rete path from αs to αt with length at most ‖Π‖(1 + O(ε)) and O(n‖Π‖) 
on- ta
t 
ongurations that 
an be 
onstru
ted from the linkages found by the pro
edure AllViableLinkages(nλ). Proof. The proof of this theorem is very similar to the proof of Theorem 4.3. These two proofs only dier in our 
hoi
e of the potential fun
tion P(Π) that assigns a value to a path Π from αs to αt. Whereas, the potential fun
tion in the proof of Theorem 4.3 only depends on the number of non-an
hor 
onta
t 
ongurations on Π (denoted c(Π)) and the viability of Π (denoted v(Π)), our new potential fun
tion also depends on the length of Π. Spe
i
ally, we dene P(Π) as ‖Π‖ + ξε2nλ[5c(Π) − 4v(Π)], for some su
iently large 
onstant ξ. Let Π∗ be a feasible ε-dis
rete path with minimum potential. By Lemma 6.3 and the same arguments 
ontained in Theorem 4.3, if some linkage of Π∗ is not dis
overed by AllViableLinkages(nλ), we 
an 
onstru
t a path Π′ su
h that c(Π′) ≤ c(Π∗)+3, v(Π′) ≥ v(Π∗) + 4, and ‖Π′‖ ≤ ‖Π∗‖ + O(ε2nλ). Hen
e, P(Π′) ≤ ‖Π∗‖ + O(ε2nλ) + ξε2nλ[5c(Π∗)−4v(Π∗)−1]. We 
an rewrite this as P(Π′) ≤ P(Π∗)+O(ε2nλ)−ξε2nλ. By making ξ su
iently large, P(Π′) must be less than P(Π∗), a 
ontradi
tion. Therefore, every linkage on Π∗ is found by AllViableLinkages(nλ). We now show that ‖Π∗‖ ≤ (1+O(ε))‖Π‖. We 
an assume without loss of generality that Π is the shortest feasible path. Then c(Π) ≤ O(n‖Π‖) by the reasoning at the beginning of the proof of Theorem 6.2. By 
hoi
e of Π∗, we know that P(Π∗) ≤ P(Π). Hen
e, ‖Π∗‖ ≤ ‖Π‖+ξε2nλ ·5O(n‖Π‖). If we assume that ε−1 ≥ ξn2λ (as was stated in the introdu
tion of this 
hapter), this inequality simplies to ‖Π∗‖ ≤ ‖Π‖ + ‖Π‖O(ε), whi
h is the desired result. Finally, we show that c(Π∗) ≤ O(n‖Π‖). Re
all that P(Π∗) ≤ P(Π) and c(Π∗) ≥ v(Π∗) (the argument for this inequality is given in Theorem 4.3). Hen
e, ‖Π∗‖ + ξε2nλc(Π∗) ≤ ‖Π‖+ 5ξε2nλc(Π). Therefore c(Π∗) ≤ 5c(Π) be
ause ‖Π∗‖ ≥ ‖Π‖. 64 Chapter 7 Con
lusion In this thesis, we presented two algorithms for nding a bounded-
urvature path amid polygonal obsta
les. These algorithms are dierent from existing algorithms for bounded- 
urvature motion-planning in that they take an input parameter (k or λ) that bounds the 
omplexity of the desired output. Given su
h a parameter, our algorithms are guar- anteed to nd a path (if one exists) in time that is polynomial in the bound on the output (k or λ), the size of the input n, and the input pre
ision m. This is an advan
e in the state-of-the-art be
ause the only other algorithm that is guaranteed to dete
t a feasible path amid arbitrary polygonal obsta
les takes exponential time in the size of the input n and input pre
ision m [17℄. Moreover, this algorithm just indi
ates whether or not a feasible path exists (it does not return a des
ription of a path), whereas our new algorithms return a des
ription of the desired path. Our algorithms dier from previous bounded-
urvature approximation algorithms in that they sear
h for paths in a non-uniform, adaptive manner. To 
larify what we mean by non-uniform, the set of environment 
onta
ts that we 
onsider is typi
ally 
on
entrated around degenera
ies (su
h as an
hors). This is dierent from the prior shortest bounded-
urvature approximation algorithms, in whi
h the set of environment 
onta
ts that are 
onsidered are distributed uniformly about ea
h feature. To 
larify what we mean by adaptive, the environment 
onta
ts that our algorithm 
onsiders are determined during the path sear
h. We prune this sear
h so that ea
h path that we extend 
overs the paths that we do not extend. Intuitively, this fo
uses attention away from easy to rea
h regions. In 
ontrast, several other bounded-
urvature motion plan- ning algorithms sele
t the 
onta
ts to be 
onsidered independent of the path sear
h [18, 2, 3, 10℄. Our su

essful appli
ation of a non-uniform, adaptive sear
h suggests that heuristi
 sear
hes 
ould be made more robust (likely to nd a path) by being non-uniform and adaptive as well: intuitively, by sear
hing more 
arefully around de- genera
ies (e.g. where an
hor 
ongurations o

ur) and less 
arefully in easy to rea
h areas, as determined by the sear
h. Our algorithms rely on two new te
hniques: the total dis
retisation of the spa
e of paths that we 
onsider and a sophisti
ated argument that allows us to prune our sear
h without sa
ri
ing 
ompleteness. We believe that both te
hniques have wider 65 appli
ation. These two te
hniques were rst developed to nd a feasible path. In this thesis, we demonstrated their wider appli
ability in 
reating an algorithm to nd an approximately shortest feasible path. Re
all from Chapter 2 that the bounded-
urvature motion restri
tion is a spe
ial type of kinodynami
 restri
tion. In the kinodynami
 setting, the question of nding an approximation to the qui
kest traje
tory in polynomial time is open. To 
larify, there are approximation algorithms, but they return approximations to the qui
kest δ-safe traje
tories. Given a δ > 0, we 
an 
ontrive a simple problem instan
e that admits a feasible traje
tory but no δ-safe traje
tory. Hen
e, it is reasonable to ask if the te
hniques in this thesis 
an be applied to remove the 
ondition of safety from the 
urrent approximation results. This is not at all 
lear. Moreover, even if it is possi- ble in prin
iple, it might not be possible in pra
ti
e be
ause the analysis be
omes too 
ompli
ated. To begin with, we would rst want to dis
retise the spa
e of traje
tories. The dis
retisations in this thesis relied heavily on Dubins 
hara
terisation of short- est bounded-
urvature paths [16℄. Unfortunately, in general, the stru
ture of qui
kest traje
tories is mu
h less understood than the stru
ture of shortest bounded-
urvature paths. Even in the one 
ase where the stru
ture is well understood (in the plane where distan
e is measured with the L∞ norm [12℄), it is un
lear how to eliminate degrees of freedom from a traje
tory by perturbation: unlike the bounded-
urvature setting, there are two degrees of freedom at an obsta
le 
onta
t be
ause the magnitude of the velo
ity 
an vary; additionally, it is un
lear how additional obsta
le 
onta
ts (something that o

urs frequently in our bounded-
urvature normalisation) eliminate freedom from a traje
tory. For similar reasons, it is un
lear our te
hniques apply to nding bounded-
urvature paths in three-dimensions: we do not 
urrently have a good understanding of what shortest bounded-
urvature paths in three-dimensions look like, and any obsta
le 
on- ta
t has two degrees of freedom in three dimensions. Note that the worst 
ase paths that a 
omplete algorithm must nd are unrealisti for real-world roboti
 appli
ations be
ause they require tou
hing obsta
les and turning with great pre
ision. The restri
tion to ε-robust paths redu
es the pre
ision required, but paths must still brush up against the environment. Re
all that a path is δ-safe if the 
entre of an δ-radius ball 
an tra
e the path without the ball tou
hing any obsta
les. This denition is distin
t from the notion of robustness: an ε-robust path is 0-safe be
ause most of its turns tou
h the environment, and there exist δ-safe solutions to problems where the only robust solutions are 0-robust. Finding an δ-safe path redu
es to problems that we have already 
onsidered by taking a Minkowski sum of the obsta
les with an δ-radius ball. Hen
e, we are 
ondent that our results 
an be generalised to nd an δ-safe bounded-
urvature path amid polygonal obsta
les in the plane in polynomially bounded time. However, the problem be
omes more interesting if we are satised with a path that is less safe: say for example, if we are satised with nding a (δ/2)-safe path, whenever a δ-safe path exists. This avenue of resear
h has been explored in the higher dimensions: there is a non-uniform dis
retisation approa
h to nding an (1 + ε) approximation to the shortest δ-safe (almost) bounded-
urvature path in three or more 66 dimensions [25℄. In this 
ase, the returned path is only guaranteed to be (δ/3)-safe. A
hieving a similar result in two dimensions is open. We are optimisti
 that rephrasing the problem in terms of safety would allow us to a
hieve asymptoti
ally better bounds than we have a
hieved in this thesis. Moreover, we feel that the restri
tion to safe paths is a more realisti
 than the restri
tion to robust paths. Shortest bounded-
urvature paths with reversals in the plane are also 
omposed of C-segments and L-segments [22℄. Finding a feasible path is less interesting in this setting be
ause we 
an approximate an given 
ontinuous path by using an arbitrary number of reversals. However, nding a path with bounded number of reversals (e.g. a path with intri
a
y at most k) is an open problem. One 
ompli
ation is that reversals 
an o

ur on an obsta
le boundary. So we no longer have just one degree of freedom when a path tou
hes a wall. Although the run times of our algorithms are a fun
tion of input pre
ision m, we have still exploited the Real RAM model of 
omputation in our analysis. This is similar to the (1 + ε) approximation algorithm developed by Papadimitriou for nding the shortest un
onstrained path amid arbitrary polyhedra in three dimensions [21℄. Subsequent work has shown that Papadimitriou's approa
h works in polynomial time in a bit model of 
omputation [14℄. It remains to be seen if our algorithms also have a polynomially bounded 
omplexity in a bit model. The loose bound on the run time of our feasibility algorithm is O(n29k2(m+ nk)3). In this thesis, we abandoned our attempts to optimise the asymptoti
 bound on the run time in order to simplify our analysis. However, the subtleties that lead to a high degree bound are real issues that any 
omplete algorithm must address. Therefore, it is not 
lear if any 
omplete algorithm 
an be asymptoti
ally 
ompetitive with the fast O(n2ε−4 log n) approximation algorithm for ε-robust paths. Our algorithms take parameters that limit the length or intri
a
y of the paths that they 
onsider. However, there is no known upper bound on the length or intri
a
y of the feasible paths in arbitrary polygonal environments, whi
h poses an open problem. If the ne
essary intri
a
y is polynomially bounded, the run times of algorithms presented here are polynomially bounded in the size of the input. Otherwise, minimising the intri
a
y is a well justied optimisation 
riteria. This is analogous to nding a minimum-link path when there are no 
onstraints on the path. Our feasibility result only nds an approximately minimum intri
a
y path. To 
larify, it returns a path with intri
a
y at most O(nk + n3), when a path of intri
a
y k exists. An open problem is to 
lose this gap: to nd a path with intri
a
y at most O(k) when a path of intri
a
y k exists. A good starting point is understanding what bounded-
urvature paths (with or without reversals) with minimum intri
a
y look like. Finding su
h a 
hara
terisation is an open problem. 67 Bibliography [1℄ Pankaj K. Agarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, and Sue Whitesides. Curvature-
onstrained shortest paths in a 
onvex polygon. SIAM Journal on Computing, 31(6):18141851, 2002. [2℄ Pankaj K. Agarwal, Prabhakar Raghavan, and Hisao Tamaki. Motion planning for a steering-
onstrained robot through moderate obsta
les. In STOC '95: Pro- 
eedings of the twenty-seventh annual ACM symposium on Theory of 
omputing, 1995. [3℄ Pankaj K. Agarwal and Hongyan Wang. Approximation algorithms for 
urvature- 
onstrained shortest paths. SIAM Journal on Computing, 30(6):17391772, 2001. [4℄ Hee-Kap Ahn, Otfried Cheong, Ji°í Matou²ek, and Antoine Vigneron. Rea
hability by paths of bounded 
urvature in 
onvex polygons. In SCG '00: Pro
eedings of the sixteenth annual symposium on Computational geometry, pages 251259, New York, NY, USA, 2000. ACM Press. [5℄ Jonathan Ba
ker and David Kirkpatri
k. Finding 
urvature-
onstrained paths that avoid polygonal obsta
les. In SCG '07: Pro
eedings of the Twenty-Third Annual Symposium on Computational Geometry, pages 6673, New York, NY, USA, 2007. ACM. [6℄ Jonathan Ba
ker and David Kirkpatri
k. A 
omplete approximation algorithm for shortest bounded-
urvature paths. In Algorithms and Computation, pages 628643. Springer-Verlag, 2008. [7℄ Mi
hael Ben-Or, Dexter Kozen, and John Reif. The 
omplexity of elementary algebra and geometry. Journal of 
omputer and system s
ien
es, 32:251, 1986. [8℄ Sergey Bereg and David Kirkpatri
k. Curvature-bounded traversals of narrow 
orridors. In SCG '05: Pro
eedings of the twenty-rst annual symposium on Com- putational geometry, pages 278287, New York, NY, USA, 2005. ACM Press. [9℄ Jean-Daniel Boissonnat, André Cérézo, and Juliette Leblond. Shortest paths of bounded 
urvature in the plane. Journal of Intelligent and Roboti
 Systems, 11(1):520, Mar
h 1994. 68 [10℄ Jean-Daniel Boissonnat and Sylvain Lazard. A polynomial-time algorithm for 
omputing shortest paths of bounded 
urvature amidst moderate obsta
les. Inter- national Journal of Computational Geometry & Appli
ations, 13(3):189229, 2003. [11℄ Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan S
hirra, and Susanne S
hmitt. A separation bound for real algebrai
 expressions. In Le
ture Notes in Computer S
ien
e: European Symposium on Algorithms 2001, volume 2161, pages 254. Springer-Verlag, January 2001. [12℄ John Canny, Ashutosh Rege, and John Reif. An exa
t algorithm for kinodynami planning in the plane. Dis
rete and Computational Geometry, 6(1):461484, De- 
ember 1991. [13℄ John Canny and John Reif. New lower bound te
hniques for robot motion planning problems. In Pro
eedings of the 28th IEEE Symposium on the Foundations of Computer S
ien
e, New York, 1987. IEEE. [14℄ Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap. Approximate eu
lidean shortest path in 3-spa
e. In SCG '94: Pro
eedings of the tenth annual symposium on Computational geometry, pages 4148, New York, NY, USA, 1994. ACM Press. [15℄ George E. Collins. Hauptvortrag: Quantier elimination for real 
losed elds by 
ylindri
al algebrai
 de
omposition. In Pro
eedings of the 2nd GI Conferen
e on Automata Theory and Formal Languages, pages 134183, London, UK, 1975. Springer-Verlag. [16℄ L. E. Dubins. On 
urves of minimal length with a 
onstraint on average 
urvature, and with pres
ribed initial and terminal positions and tangents. Amer. J. Math., 79:497516, 1957. [17℄ Steven Fortune and Gordon Wilfong. Planning 
onstrained motion. Ann. Math. Arti
ial Intelligen
e, 3(1):2182, 1991. Algorithmi
 motion planning in roboti
s. [18℄ Paul Ja
obs and John Canny. Planning smooth paths for mobile robots. In Pro- 
eedings of the 1989 IEEE International Conferen
e on Roboti
s and Automation, pages 27, 1989. [19℄ David S. Johnson. The NP-
ompleteness 
olumn. Journal of Algorithms, 3(1):182 195, 1982. [20℄ Jean-Claude Latombe. Robot Motion Planning (The Springer International Series in Engineering and Computer S
ien
e). Springer, De
ember 1990. [21℄ Christos H. Papadimitriou. An algorithm for shortest-path motion in three dimen- sions. Inform. Pro
ess. Lett., 20(5):259263, 1985. 69 [22℄ J. A. Reeds and L. A. Shepp. Optimal paths for a 
ar that goes both forwards and ba
kwards. Pa
i
 J. Math., 145(2):367393, 1990. [23℄ John Reif and Hongyan Wang. The 
omplexity of the two dimensional 
urvature- 
onstrained shortest-path problem. In WAFR '98: Pro
eedings of the third work- shop on the algorithmi
 foundations of roboti
s on Roboti
s : the algorithmi
 per- spe
tive, pages 4957, Nati
k, MA, USA, 1998. A. K. Peters, Ltd. [24℄ John H. Reif and James A. Storer. A single-exponential upper bound for nding shortest paths in three dimensions. J. ACM, 41(5):10131019, 1994. [25℄ John H. Reif and Hongyan Wang. Nonuniform dis
retization for kinodynami motion planning and its appli
ations. SIAM J. Comput., 30(1):161190, 2000. [26℄ Jürgen Sellen, Joonsoo Choi, and Chee-Keng Yap. Pre
ision-sensitive eu
lidean shortest path in 3-spa
e. SIAM Journal on Computing, 29(5):15771595, 2000. [27℄ Mi
ha Sharir. Algorithmi
 motion planning. In Ja
ob E. Goodman and Joseph O'Rourke, editors, Handbook of Dis
rete and Computational Geometry, 
hapter 57, pages 10371064. CRC Press LLC, Bo
a Raton, FL, 2004. [28℄ Mi
ha Sharir and Amir S
horr. On shortest paths in polyhedral spa
es. In STOC '84: Pro
eedings of the sixteenth annual ACM symposium on Theory of 
omputing, pages 144153, New York, NY, USA, 1984. ACM Press. [29℄ Gordon T. Wilfong. Motion planning for an autonomous vehi
le. In Pro
eedings of IEEE International Conferen
e on Roboti
s and Automation, pages 529533, 1988. 70 Appendix A Jumps between Corners In this appendix we prove several properties of jumps from a 
orner F to a 
orner G. These properties allows us to dene su
ient 
onditions to guarantee that two jumps do not 
ross. We use them to prove the 
orre
tness of our approa
h to ltering 
ongurations. The rst main result of this appendix states that all jumps are 
ontained in a region R between F and G (see Lemma A.1). This region R has the property that any jump J from F to G splits R into two smaller regions S1 and S2. These smaller regions 
orrespond to dierent sides of J and satisfy the following property: if jump K is on one side of J (i.e. K ⊆ S1) and jump K ′ is on the other side (i.e. K ′ ⊆ S2), then K and K ′ do not 
ross. The se
ond main result is a su
ient 
ondition to guarantee that two jumps do not 
ross (see Lemma A.2): if two jumps K and K ′ from F to G share a 
ommon sour
e 
onguration or a 
ommon destination 
onguration, then K and K ′ do not 
ross. A.1 Sides of a Jump We rst argue that all jumps from a 
orner F to a 
orner G are 
ontained in one region R dened as follows: let R1 be the region swept out by a radius two dis
 whose 
entre tra
es the line segment between F and G; let R2 be the portion of the line through F and G that is not between F and G; then let R = R1 \R2 (see Figure A.2(b)). Lemma A.1. Every jump J from F to G is 
ontained in a region R. The region R is su
h that any su
h J splits R into two regions, 
alled the sides of J . Proof. We rst show that the L-segments of su
h jumps are 
ontained inR. Let J (θ) be the set of jumps from F to G where the L-segment points in dire
tion θ (see Figure A.1). Let J be an arbitrary jump in J (θ). As we tra
e a point on the L-segment of J in the dire
tion of the L-segment, the point gets progressively farther from F and 
loser to G. This is true be
ause the sour
e and destination C-segments of J have length at most π. Hen
e, the L-segment of J lies in the interse
tion of two half planes (see Figure A.1(a)): 71 the boundary of the rst half-plane starts at F and the half-plane points in the dire
tion of θ; the boundary of the se
ond half-plane starts at G and the half-plane points in opposite dire
tion of θ. We also note that an L-segment of J starts at most two units from F be
ause the sour
e C-segment has length at most π (see Figure A.1(b)). Hen
e the L-segment is 
ontained in the light shaded region of Figure A.1(b). Similarly, the L-segment of J ends at most two units from G. F G (a) L-segments of jumps get farther from F and 
loser to G. F G (b) L-segments start at most two units from F . Figure A.1: Jumps from F to G with L-segments pointing in one xed dire
tion. Combining all of our observations so far, the L-segment of J must lie in the darkly shaded parallelogram of Figure A.2(a). We overestimate this region with the lightly shaded parallelogram: two sides are parallel to the line through F and G; the other two sides are perpendi
ular to θ. The union over all θ of these overestimates is R (see Figure A.2(b)). This region has two small slits be
ause our arguments are overestimates: L-segments rarely rea
h the interior of the sides of our bounding parallelograms that are perpendi
ular to θ (just at F and G). A more rened analysis shows if there is a jump from F to G where the L-segment is dire
ted verti
ally (perpendi
ular to the line through F and G), the distan
e between F and G is exa
tly two or four; in these 
ases, the L-segment is 
ontained in R. It remains to be shown that jump C-segments are 
ontained in the shaded regions. If we ignore the slits, the C-segments are 
learly in this region be
ause every point on a jump C-segment is at most two units from a 
orner. To see that C-segments do not 
ross these slits, 
onsider the lo
us of jumps starting with a 
ounter
lo
kwise oriented C-segment (see Figure A.3). This pi
ture proves that a 
ounter
lo
kwise oriented sour
e C-segment 
annot 
ross a slit: if the sour
e C-segment interse
ts the slit tou
hing F , G is 
ontained in the unbounded region that 
annot be rea
hed; if this sour
e C-segment 
rosses the slit tou
hing G, then G is 
ontained in the unit radius 
ir
le that 
annot be rea
hed. By verti
ally ree
ting Figure A.3, it is 
learly true that 
lo
kwise oriented 72 F G (a) The L-segments of J (θ) lie in the dark shaded region. We overestimate it with light shaded region. (b) The union of our overestimate for all θ is R. Figure A.2: L-segments are 
ontained in R. sour
e C-segments 
annot 
ross either slit. By reversing the jumps and inter
hanging the roles of F and G, the same arguments show that the destination C-segments 
annot 
ross either slit. Figure A.3: Points rea
hed by a jump starting with a 
lo
kwise oriented C-segment. A.2 Non-Crossing Condition In this se
tion we prove the following lemma. Lemma A.2. Let J and K be two jumps from F to G. If J and K share the same sour
e 
onguration or the same destination 
onguration, then J and K do not 
ross. By reversal of J and K, we only need to 
onsider the 
ase where J and K have a 
ommon destination 
onguration. We start by proving a mu
h weaker result: if the rst C-segments of J and K have the same orientation and the se
ond C-segments of J and K have the same orientation, then J and K do not 
ross. We prove this by 
onsidering two distin
t 
ases: either the 73 C-segments of J have the same orientation (see Lemma A.3) or the C-segments of J have a dierent orientations (see Lemma A.4). Lemma A.3. Jumps with signed stru
ture C+LC+ from a 
orner to a 
onguration do not 
ross. Proof. Let c be the 
orner that the jumps leave from and O be the underlying 
ir
le that all of the jumps rea
h. We assume without loss of generality that c and the 
entre of O lie on the x-axis (translation and rotation), that c is left of the 
entre of O (horizontal ree
tion), and that O is 
lo
kwise oriented (verti
al ree
tion). c (a) C-segments from c do not 
ross. O (b) L-segments to O do not 
ross. Figure A.4: Segments of the same type do not 
ross. Two sour
e C-segments from c do not 
ross be
ause the C-segments have length at most π (see Figure A.4(a)). Two L-segments rea
hing O do not 
ross (see Figure A.4(b)). Hen
e any 
rossing between two jumps must o

ur between the sour
e C- segment of one jump and the L-segment of the other. C c OX o p q U T (a) Range of jumps. p c X O q T Lp Cq o (b) Ordering of jumps. Figure A.5: Jumps from c to O starting with a 
lo
kwise C-segment. We represent ea
h jump from c to O by the 
entre of its initial underlying 
ir
le. Every initial underlying 
ir
le 
entre lies on a unit-radius 
lo
kwise-oriented 
ir
le C 
entred at c (see Figure A.5(a)). The restri
tion that the sour
e C-segment has length at most π further restri
ts ea
h 
ir
le 
entre to the 
lo
kwise-oriented ar
 X. This ar X 
an be dened as follows: let p be a point of C and T be the oriented line tangent to C at p; then p ∈ X if and only if the 
ir
le 
entre o of O is not on the right-hand side 74 of T . Hen
e, X is bounded by tangent points p and p′ where the 
orresponding tangent lines T and T ′ 
ontain pass through o. Figure A.5(b) illustrates two jumps from c to O with sour
e underlying 
ir
le 
entres p and q. We order these 
entres by the orientation of X. In this 
ase, p 
omes before q. The C-segment Cq of a later jump does not interse
t the L-segment Lp of an earlier jump (see Figure A.5(b)): draw a line T from the 
entre p of the 
ir
le underlying D to o; then T is parallel to Lp, and they are exa
tly one unit apart; moreover, T splits X into two parts by the geometri
 denition of X given in the previous paragraph; so T splits q and Lp be
ause Lp lies entirely to one side of T and q 
omes after p on X; this veries that q is more than one unit away from Lp; hen
e, Cq does not interse
t Lp. c O q X p Lq Cp b (a) L-segment 
ontained in 
onvex region. c O bq′ q o T ′ T B C X Lq p (b) M starts from 
ir
le 
entered at p. Figure A.6: Earlier C-segment does not 
ross later L-segment. We now show that the C-segment Cp of an earlier jump does not interse
t the L- segment Lq of a later jump (see Figure A.6(a)). If both endpoints of Lq are in the 
onvex gray region of Figure A.6(a), then Lq does not 
ross the boundary, whi
h 
ontains Cp. Clearly the last endpoint of Lq is in the 
onvex region. Figure A.6(b) explains why the rst endpoint b of Lq is in the region: let T be a line from q to the 
entre o of O; then T is parallel to Lq, and both are exa
tly one unit apart; hen
e, the unit-radius 
ir
le B 
entred at b is 
ompletely to the left of T ′; let C be the unit 
ir
le 
entred at c; 
learly q is on both C and B; let q′ be the other point 
ommon to C and B; then q′ is left of T be
ause q′ is on B and B is left of T . Let T ′ be parallel to T but through q′; then T ′ is left of T ; hen
e o is right of T ′ be
ause T ′ and T are parallel; this 
erties that q′ is not on X; let p be a point of X that 
ome before q; then p is on the ar
 of C from q′ to q; therefore p is 
ontained in B (i.e. p is less than one unit away from b). Lemma A.4. Jumps of type C−LC+ from a 
orner to a 
onguration do not 
ross. Proof. We prove that jumps starting with a 
ounter
lo
kwise-oriented C-segment from a 
orner c to a 
lo
kwise-oriented unit-radius 
ir
le O do not 
ross. The arguments are similar to the previous proof but have a few additional 
ompli
ations. As before, the sour
e C-segment of one jump 
annot 
ross the sour
e C-segment of another, and the L-segment of one jump 
annot 
ross the sour
e C-segment of another. Hen
e, any 75 
rossing must o

ur between a sour
e C-segment of one and a L-segment of another. Our proof shows that this 
annot happen. c O X O′ C q p o UT (a) Distan
e from c to o less than three. O c q p O′ X C T U o (b) Distan
e from c to o greater than three. Figure A.7: Range of jumps from c to O starting with a 
ounter
lo
kwise C-segment. One 
ompli
ating fa
tor is that there is a qualitative dieren
e in the way in whi
h the range of jumps from c to O is bounded that depends on the distan
e from c to the 
entre o of O. If the distan
e is less than three, then the range of jumps is bounded by a jump with a zero-length sour
e C-segment and a jump with a zero-length L-segment (see Figure A.7(a)). If the distan
e is greater than three, then the range is bounded by a jump with a zero-length sour
e C-segment and a jump with a π-length sour
e C-segment (see Figure A.7(b)). As before, we represent jumps from c to O by the 
entres of their sour
e underlying 
ir
les. Let the 
ounter
lo
kwise oriented ar
 X be the domain of sour
e underlying 
ir
le 
entres. Figure A.8 illustrates two jumps represented by 
entres p and q. As before, we order jumps by the order of their initial underlying 
ir
le 
entres on X. In this 
ase, p 
omes before q. In this proof, we rely on two properties of X. Fa
t A.5. Let O′ be the 
lo
kwise-oriented radius-two 
ir
le 
entred at o. Suppose that p ∈ X. Then 1. the oriented line T from p and tangent to O′ interse
ts X on
e, and (a) the oriented half line T ′ emanating from X and tangent to X at p does not interse
t O'. Proof. The rst property results from the restri
tion that the sour
e C-segment has length at most π: in general, T interse
ts the unit-radius 
ir
le 
entred at c twi
e; ea
h of these interse
tions 
orresponds to a type C−L path from c to O, but only one of these paths has a C-segment with length at most π. The se
ond property is a 
onsequen
e of the rst: rotate T away from O′ about p until it be
omes tangent to X. The sour
e C-segment Cq from a later jump does not 
ross the L-segment Lp of an earlier jump (see Figure A.8): let T be the oriented line from p and tangent to O′; then T is parallel to Lp, and both are exa
tly one unit apart; moreover, T splits X into two 76 TpX q O c O′ Lp Cq Figure A.8: Later C-segment does not 
ross earlier L-segment. pie
es; in parti
ular, q and Lp are on dierent sides of T ; hen
e q is at least one unit from Lp; therefore Cq does not 
ross Lp. We now show that sour
e segment C-segment Cp of an earlier jump does not 
ross the L-segment Lq of a later jump. This argument 
onsists of two distin
t parts: the 
ir
le underlying Cp 
ontains the rst endpoint of Lq, and Lq 
annot 
ross Cp be
ause the relevant parts of Lq are 
ontained in a 
onvex region bounded by Cp. T ′ T q q′ O′ O c b o Lq C B X (a) Later L-segment starts from earlier underlying 
ir
le. O p q Lq Cp X P b c m (b) Relevant part ofM 
ontained in 
onvex region. Figure A.9: Earlier C-segment does not 
ross later L-segment First, let b be the initial endpoint of an L-segment Lq of a jump represented by q (see Figure A.9(a)). Let B be the unit-radius 
ir
le 
entred at b. To 
omplete the rst part of our proof, it su
es to show that every point of X before q is 
ontained in B. Let T be the oriented line from q and tangent to O′. Then T is parallel to Lq. Moreover, B is 
ompletely to the right of T . Let C be the 
ounter
lo
kwise-oriented unit-radius 
ir
le 
entred at c. Clearly q is on both C and B. Let q′ be the other point 
ommon to C and B. Then q′ is right of T be
ause B is right of T . Let T ′ be the half line from q′ tangent to C. Then T is parallel to T ′. Hen
e, T ′ is right of T be
ause T ′ 
ontains q′ whi
h is right of T . The distan
e between T and T ′ is less than two be
ause the distan
e between q′ and q is less than two. Hen
e, T ′ interse
ts O′ be
ause T ′ and T are on the same side of T . Thus q′ 6∈ X by Fa
t A.5. The range of C from q′ to q is 
ontained in B. Therefore, all of X that 
omes before q is 
ontained in B. We now show that Lq does not 
ross Cp (see Figure A.9(b)). Let P be the line underlying Lp of the earlier jump represented by p. Let D be the 
ir
le underlying the C-segment Cp. Then D is on the left of P and O is on the right. We know that Lq 77 
rosses P be
ause it starts inside D and ends at O. However, the part of Lq on the right side of P is irrelevant be
ause it 
annot 
ross D. The point m where Lq 
rosses P must be after the L-segment Lp of the earlier jump p be
ause the half lines in Figure A.4(b) do not interse
t. So m is on the boundary of the shaded 
onvex region in Figure A.9(b). The part of Lq that 
an 
ross Cp is between b and m. However, b and m are in the shaded 
onvex region, whi
h has Cp on the boundary. Therefore Cp and Lq do not 
ross. We now generalise our non-
rossing 
ondition to jumps whose se
ond C-segments have the same orientation. Corollary A.6. Jumps of with signed stru
ture CLC+ from a 
orner to a 
onta
t 
onguration at a wall do not 
ross. Proof. Let J1 and J2 be two su
h jumps. If J1 and J2 start with a 
lo
kwise-oriented C-segment, they do not 
ross by Lemma A.3. If they both start with a 
ounter
lo
kwise- oriented C-segment, they do not 
ross by Lemma A.4. φ (a) Jumps with signed stru
- ture C+LC+. φ (b) Jumps with signed stru
- ture C−LC+. φ (
) Jumps with ne stru
ture C0LC + . Figure A.10: Lo
us of points rea
hing a 
onguration φ. Otherwise, there is a type C0LC + jump S from the 
orner to the 
ommon 
ong- uration (see Figure A.11): Let φ be the destination 
onguration 
ommon to J1 and J2. Figure A.10(a) shows the lo
us of points that 
an rea
h φ via a jump with C +LC+ signed stru
ture. Figure A.10(b) shows the lo
us of points that 
an rea
h φ via a jump with C−LC+ signed stru
ture. The interse
tion of these two regions is the lo
us of points that 
an rea
h φ via a jump with C0LC + ne stru
ture (see Figure A.10(
)). Let R be the region that 
ontains J1, J2, and S indi
ated by Lemma A.1. Then S splits R into two pie
es (see Figure A.11). Ea
h jump Ji is 
ontained in some pie
e be
ause Ji does not 
ross S by Lemma A.3 and Lemma A.4. Moreover, the sour
e orientations J1 and J2 point to dierent sides of S, so J1 and J2 lie in dierent pie
es of S. Hen
e, J1 and J2 do not 
ross. We are now ready to prove Lemma A.2. Re
all that it su
es to prove that two jumps J1 and J2 that end with the same 
onguration φ do not 
ross. If the orientations of the se
ond C-segments of J1 and J2 are the same, they do not 
ross by Corollary A.2. 78 SJ2 J1 Figure A.11: The jump S 
erties that J1 and J2 do not 
ross. Otherwise, there is a type CLC0 jump S from the 
orner to φ (see Figure A.12(
)): Figure A.12(a) shows the lo
us of points that 
an rea
h φ via a jump with CLC+ signed stru
ture. The verti
al ree
tion of this represents the lo
us of points that 
an rea
h φ via a jump with CLC− signed stru
ture. The interse
tion of these two regions is the lo
us of points that 
an rea
h φ via a jump with CLC0 ne stru
ture (see Figure A.12(b)). φ (a) Lo
us of jumps with signed stru
ture CLC+ that rea
h φ. φ (b) Lo
us of jumps with ne stru
ture CLC0 that rea
h φ. S J1 J2 φ (
) The jump S 
erties that J1 and J2 do not 
ross. Figure A.12: Jumps to the same 
onguration φ do not 
ross. Let R be the region that 
ontains J1, J2, and S indi
ated by Lemma A.1. Then S splits R into two pie
es (see Figure A.12(
)). Ea
h jump Ji is 
ontained in some pie
e be
ause Ji does not 
ross S by Corollary A.6. Moreover, J1 and J2 are on dierent sides of S be
ause the orientations of the se
ond C-segments of J1 and J2 are dierent. Hen
e, J1 and J2 do not 
ross. 79 Appendix B Links between Corners In this appendix, we restri
t our analysis to links of a parti
ular ne stru
ture between two 
orners F and G. Consider, for example, the set of links with stru
ture C−L0C+ illustrated in Figure B.1. Within this 
ontext, we will show three main results: if you roll the sour
e 
onguration in a 
lo
kwise dire
tion, the destination 
onguration deforms in a 
lo
kwise dire
tion (see Lemma B.1); no two links 
ross (see Lemma B.2); and there are O(n) homotopy 
lasses of links amid polygonal obsta
les (see Lemma B.3). F G Figure B.1: A range of C−L0C+ stru
ture links from F to G. B.1 Link Monotoni
ity In this se
tion, we prove the following. Lemma B.1. Links of a xed ne stru
ture Γ from one 
orner to another are mono- toni
. That is, rolling the sour
e 
onguration 
ounter
lo
kwise always 
auses the des- tination 
onguration to turn 
lo
kwise. We prove this lemma by 
onsidering ea
h type Γ of link between 
orners. We re- du
e the number of 
ases that we 
onsider through symmetry. First we note a strong 
orresponden
e between links with stru
ture C−pi LC − and C0LC + : for every link with 80 stru
ture C0LC + , we obtain a 
orresponding link with stru
ture C−pi LC − by ree
t- ing the sour
e and destination 
ongurations through their 
onta
ts (see Figure B.2). Hen
e, we do not expli
itly links with stru
ture C±pi LC ± and C±LC±pi be
ause they are symmetri
 to other 
ases that we 
onsider. 0LC piLC Figure B.2: Same underlying 
ir
le 
entres. We assume without loss of generality that the 
orners lie on the x-axis (by suitable rotation and translation). We denote the distan
e between the 
orners ∆. B.1.1 Links with Stru
ture C0LC and CLC0 The reverse of link with stru
ture C0LC has stru
ture CLC0, so we only 
onsider the former. We assume without loss of generality that the C-segment tou
hes the 
orner on the right (by a horizontal ree
tion) and that the nal C-segment is oriented 
lo
kwise (by a verti
al ree
tion). Figure B.3 shows two links with stru
ture C0LC + . Our analysis fo
uses on a quadrilateral formed by the underlying 
ir
le 
entres and 
orners. 1 1 e ∆ θ γ φ (a) Non-self-interse
ting quadrilateral. s 1 1 e γ −φ θ ∆ (b) Self-interse
ting quadrilateral. Figure B.3: Monotoni
ity of links with stru
ture C0LC + . We rst look at the proje
tions of the sides adja
ent to φ onto the side perpendi
ular to the side of length e. sin γ +∆cos θ = 1 (B.1) cos γ · dγ dθ −∆sin θ = 0 dγ dθ = ∆sin θ cos γ (B.2) 81 Then we look at the proje
tions of the sides adja
ent to φ onto the side of length e. ∆sin θ = e+ cos (π − γ) cos γ +∆sin θ = e (B.3) The sum of the interior angles of a quadrilateral is 
onstant. θ + π 2 + γ + φ = 2π 1 + dγ dθ + dφ dθ = 0 dφ dθ = − ( 1 + ∆ sin θ cos γ ) by Equation B.2 = −cos γ +∆sin θ cos γ = − e cos γ by Equation B.3 This tells us monotoni
ity of φ relative to θ is governed by the sign of cos γ. Looking at Figure B.3, we see that γ is π/2 plus the length of the C-segment. Hen
e, pi 2 ≤ γ ≤ 3pi 2 , whi
h means that cos γ is always negative. So φ always in
reases with θ. B.1.2 Links with Stru
ture C±LC∓pi and C ± pi LC ∓ The reverse of link with stru
ture C±LC∓pi is a link with stru
ture C ± pi LC ∓ , so we only 
onsider the latter. We assume, without loss of generality, that the π length C-segment starts at the left 
orner (by a horizontal ip) and that the left C-segment is 
ounter- 
lo
kwise oriented (by a verti
al ip). Again, our analysis fo
uses on a 
onstrained quadrilateral. ∆ 3 e 1 θ φ γ Figure B.4: Monotoni
ity of links with stru
ture C−pi LC + . The geometry underlying a link with stru
ture C−pi LC + (see Figure B.4) is very similar to the geometry underlying a link with stru
ture C0LC + (see Figure B.3): the length three side in the former gure has length one in the latter. Fortunately, the same analysis works be
ause the derivative of the 
onstant length in Equation B.1 is zero regardless of the value (zero or three). 82 B.1.3 Links with Stru
ture CL0C We rst examine the relationship between angles of an arbitrary quadrilateral when the side lengths are xed (see Figure B.5). Then we use those results to show that a link with stru
ture CL0C is monotoni
. α β γ δ ~a ~b ~c ~d Figure B.5: Arbitrary quadrilateral expressed as ve
tors and angles. Let ~uand ~v be ve
tors in the plane. Dene ~u · ~v = ‖~u‖ ‖~v‖ cos θ and ~u × ~v = ‖~u‖ ‖~v‖ sin θ, where θ is the 
lo
kwise angle from u to v. In parti
ular, the dot produ
t is 
ommutative (~u ·~v = ~v ·~u) but the 
ross produ
e is not quite (~u×~v = −~v×~u). Both of these produ
ts are distributive. We rst derive Equation B.4 that has a simple geometri
 interpretation when the quadrilateral is simple: the quadrilateral in Figure B.5 has two triangulations; the sum of the areas of one de
omposition are the same as the sum of the areas of the other de
omposition. ~a+~b+ ~c + ~d = 0 ~a+ ~c = − ( ~b+ ~d ) (~a+ ~c)× ( ~b+ ~d ) = 0 ~a×~b+ ~a× ~d+ ~c×~b+ ~c× ~d = 0 ~a×~b+ ~c× ~d = − ~a× ~d− ~c×~b = ~b× ~c+ ~d× ~a (B.4) We now derive the derivative of opposite angles in the quadrilateral (see Equation B.6). ~a+~b+ ~c + ~d = 0 ~a+~b = − ( ~c+ ~d ) (B.5)( ~a+~b ) · ( ~a+~b ) = ( ~c+ ~d ) · ( ~c+ ~d ) ~a · ~a+ 2~a ·~b+~b ·~b = ~c · ~c+ 2~c · ~d+ ~d · ~d d dα ( ~a ·~b ) = d dα ( ~c · ~d ) d dα ( ‖~a‖ ∥∥∥~b∥∥∥ cosα) = d dα ( ‖~c‖ ∥∥∥~d∥∥∥ cos γ) 83 −‖~a‖ ∥∥∥~b∥∥∥ sinα = −dγ dα ‖~c‖ ∥∥∥~d∥∥∥ sin γ dγ dα = ~a×~b ~c× ~d (B.6) By relabelling, dδ dβ = ( ~b× ~c ) / ( ~d× ~a ) . Assume that the sum α + β + γ + δ is some 
onstant multiple C of 2π. This not true in general be
ause of the 
y
li
 nature of angle parameterisation: for example, as an angle passes through 0 to 2π the 
onstant must 
hange. However, we 
an make it hold lo
ally (around values 
lose to the original values) by reparameterising the angles as ne
essary (e.g. [−π, π) instead of [0, 2π)). α + β + γ + δ = 2Cπ α + γ = 2Cπ − (β + δ) d dα (α + γ) = −dβ dα · d dβ (β + δ) 1 + dγ dα = dβ dα [ −1− dδ dβ ] 1 + ~a×~b ~c× ~d = − dβ dα  1 + ~b× ~c ~d× ~a   by EquationB.6 ~a×~b+ ~c× ~d ~c× ~d = − dβ dα  ~b× ~c+ ~d× ~a ~d× ~a   dβ dα = −  ~a×~b+ ~c× ~d ~b× ~c+ ~d× ~a     ~d× ~a ~c× ~d   = − ~d× ~a ~c× ~d by EquationB.4 We now 
onsider links with stru
ture CL0C. We assume, without loss of generality, that the link goes from left 
orner to right 
orner (by a horizontal ip) and that the left C-segment is oriented 
lo
kwise (by a verti
al ip). We have labelled the quantities relevant to analysis in Figure B.6. Note that π−δ is the length of the initial C-segment. So 0 ≤ π − δ ≤ π. Hen
e, 0 ≤ δ ≤ π. Similarly, γ − π is length of the nal C-segment. So 0 ≤ γ − π ≤ π. Hen
e, π ≤ γ ≤ 2π. Now dβ dα = −‖d‖ ‖a‖ sin δ‖c‖ ‖d‖ sin γ = − 2 sin δ 2 sin γ whi
h is non-positive for δ ∈ [0, π] and γ ∈ [π, 2π]. 84 βδ γ α 1 ∆ 1 2 Figure B.6: CL0C-link monotoni
ity. B.2 Non-Crossing Links In this se
tion, we argue that links with the same ne stru
ture do not 
ross. Lemma B.2. Let J be the set of links from 
orner F to 
orner G with ne stru
ture Γ. Then no two links of J 
ross. Proof. We 
an refer to ea
h link of J by its sour
e 
onguration: re
all that any jump is uniquely determined by its sour
e 
onguration θ, destination 
onguration φ, and ne stru
ture Γ; by Lemma B.1, there is exa
tly one φ given θ. Ea
h sour
e 
onguration 
an be represented by a number in (−π, π] indi
ating how its orientation diers from the dire
tion from F to G. By referen
e to ea
h link of J by its sour
e 
onguration, we 
an treat J as a subset of (−π, π]. Our proof relies on one 
riti
al observation: for ea
h J ∈ J , there is a non-empty two-sided neighbourhood around J su
h that no link in this neighbourhood 
rosses J . The details verifying that this is true depends on the ne stru
ture Γ. We only 
onsider the 
ase when Γ = C−L0C+ be
ause the other 
ases are similar. As illustrated by Figure B.7, we 
an derive a jump S− with stru
ture C−LC+ from J by slightly rolling the sour
e 
onguration of J in a 
ounter
lo
kwise dire
tion. There is a J− ∈ J with the same sour
e 
onguration as S− that we 
an derive by rolling the destination 
onguration of S− 
lo
kwise until the L-segment of S− disappears. By Lemma A.2, neither J− nor J 
ross S−. By 
onstru
tion, J− and J are on dierent sides of S− (see Lemma A.1). Hen
e J− and J do not 
ross. Therefore, there is a non-empty neighbourhood on one side of J that does not 
ross J . A similar argument holds for jumps J+ on the other side of J . Let J0 be an arbitrary link of J . We now argue that no link of J 
rosses J0. Then let K be the subset of J that 
rosses with J0. If K = ∅, we are done. Otherwise, by reversing the order of J as ne
essary, we assume without loss of generality that there exists some jump K ∈ K su
h that J0 < K. Let J2 be the greatest lower bound of {K ∈ K : J0 < K}. We now argue that J0 does not 
ross J2. This is trivially true if J0 = J2. So suppose J0 6= J2. Consider a jump J1 in the neighbourhood of J2 su
h that J0 < J1 < J2 and J1 does not 
ross J2. Noti
e that J1 does not 
ross J0 by denition of J2. Thus, J0 does not 
ross J2 be
ause J0 and J2 lie on dierent sides of J1. 85 FG J+ J S+ J− R S− Figure B.7: Links J− and J+ that are 
lose to J do not 
ross J . Let N be a non-empty two-sided neighbourhood of J2 su
h that any jump of N does not 
ross J2. Let J3 ∈ N be su
h that J2 < J3 . Then J1 does not 
ross J3 be
ause J1 and J3 are on dierent sides of J2. Therefore, the existen
e of N 
ontradi
ts that J2 is a greatest lower bound. B.3 Number of Homotopy Classes We now argue that there are only a bounded number of homotopy 
lasses of links. Lemma B.3. Let J be the set of links from 
orner F to 
orner G with ne stru
ture Γ. Then there are O(n) homotopy 
lasses of J . Proof. By Lemma B.2, no two links of J 
ross. This implies a natural order < on J , where Ju < Jv < Jw implies that Ju and Jw are on dierent sides of Jv (see Lemma A.1). Hen
e the homotopy 
lasses of J have a natural order: suppose that Ju < Jv < Jw, Ju and Jv are homotopi
, and Jv and Jw are homotopi
; then Ju and Jw are homotopi be
ause Ju and Jw lie on dierent sides of Jv. This ordering of homotopy 
lasses implies that are O(n) homotopy 
lasses be
ause ea
h feature separates at most two 
onse
utive homotopy 
lasses. 86 Appendix C Convergen
e to a Fixed-Point In this 
hapter, we prove Theorem 5.5. Let ∆ represent the distan
e between 
orners F and G. We split our analysis a

ording to whether ∆ < 2 or ∆ ≥ 2. The te
hniques that we use in ea
h 
ase are similar, but we make dierent 
ompromises when balan
ing inequalities. In Theorem 5.5, we get quadrati
 
onvergen
e after O(m) iterations when ∆ 6= 2. The input pre
ision m is part of the statement of the result be
ause we use m to push ∆ away from zero and two. Lemma C.1. If ∆ 6= z, then |∆− z| ≥ 2−O(m), for integers z with magnitude at most 2m. Proof. Follows immediately from Corollary 5.7 be
ause ea
h 
orner 
oordinate is given as the ratio of two integers, ea
h with magnitude at most 2m. C.1 Forward Iteration (∆ < 2) dj cj cj+1 L T d∞ dj+1 H I Figure C.1: Forward iteration approximation. We now prove the rapid 
onvergen
e of 〈di〉 to d∞. Figure C.1 illustrates how we 
onstru
t dj+1 from dj. Let H be the unit-radius 
ir
le 
entred at F . Let T be the line tangent to H at dj. Let L be the lo
us of points that are equidistant to F and G. The point dj+1 is the horizontal proje
tion onto H of the interse
tion of T and L. 87 Let the fun
tion f (y) map the y-
oordinate y of dj to the y-
oordinate of dj+1. Then f is a single Newton-Raphson iteration 
onverging to the y-
oordinate of d∞. We now derive an expression for f(y): the slope of the line through the origin and dj is y (1− y2)−1/2; hen
e, the slope of T is − (1− y2)1/2 y−1 be
ause T is perpendi
ular to that line; the 
oordinates of the the interse
tion of L and T are (∆/2, f (y)), so − ( 1− y2 )1/2 y−1 = (f (y)− y) ( ∆ 2 − [ 1− y2 ]1/2)−1 y (f (y)− y) = ( 1− y2 )1/2 ([ 1− y2 ]1/2 − ∆ 2 ) f (y) y − y2 = [ 1− y2 ] − ∆ 2 [ 1− y2 ]1/2 f (y) y = 1 2 ( 2−∆ √ 1− y2 ) f (y) = 1 2 ( 2−∆ ( 1− y2 )1/2) y−1 (C.1) Lemma C.2. The rea
h of d−1 and d1 overlap. Proof. Let y±1 be the y-
oordinate of d±1. Then overlap happens if f (y−1) ≥ y1. This is equivalent to y21 ≤ f (y−1)2 be
ause both f (y−1) , y1 ≤ 0. Now y−1 = − ( 1− (∆/5)2 )1/2 and y1 = − ( 1− (∆/3)2 )1/2 (see Figures 5.7(b) and 5.8(a)). So f (y−1) 2 = 1 4 ( 2−∆ ( 1− y2−1 )1/2)2 y−2−1 = 1 4 ( 2−∆ ( 1− [ 1− (∆/5)2 ])1/2)2 [ 1− (∆/5)2 ]−1 = 1 4 (2−∆(∆/5))2 [ 1− (∆/5)2 ]−1 = (2−∆(∆/5))2 [ 4− 4 (∆/5)2 ]−1 = ( 4− 4∆ (∆/5) + ∆2 (∆/5)2 ) [ 4− (2∆/5)2 ]−1 = ( 100− 20∆2 +∆4 ) [ 100− 2∆2 ]−1 Re
all that we want f (y−1) 2 ≤ y21( 100− 20∆2 +∆4 ) [ 100− 2∆2 ]−1 ≤ [1− (∆/3)2] 100− 20∆2 +∆4 ≤ [ 1− (∆/3)2 ] [ 100− 2∆2 ] 88 9 ( 100− 20∆2 +∆4 ) ≤ [ 9−∆2 ] [ 100− 2∆2 ] 900− 180∆2 + 9∆4 ≤ 900− 18∆2 − 100∆2 + 2∆4 −180∆2 + 9∆4 ≤ −118∆2 + 2∆4 7∆4 − 62∆2 ≤ 0 ∆2 ( 7∆2 − 62 ) ≤ 0 7∆2 ≤ 62 whi
h is true be
ause ∆ < 2. In the rest of this subse
tion, we prove the following theorem. Theorem C.3. The error measure ξ+ (j) = y∞−yj de
reases very rapidly. In parti
ular 1. If ∆ ∈ (0, 2], then ξ+ (j) ≤ 2−Ω(j), for j > 1. 2. If ∆ ∈ (0, 2), then ξ+ (j) ≤ 2−2Ω(j) , for j > O(m). Proof. By Taylor's Theorem, f(y) = f (y∞) + f ′ (u) (y − y∞), for some u ∈ [y, y∞]. Using this expansion, the error term ξ+ (j + 1) = y∞ − f (yj) be
omes y∞ − f (y∞) − f ′ (u) (yj − y∞) = −f ′ (u) (yj − y∞) = f ′ (u) · ξ+ (j). Corollary C.5 bounds f ′ (u) ∈[ 0, 3 5 ] , for ∆ ∈ (0, 2]. Hen
e, ξ+ (j + 1) ≤ 35ξ+ (j). Now ξ+ (j) ≤ 1, so ξ+ (j) ≤( 3 5 )j−1 = [( 3 5 )2](j−1)/2 = [ 9 25 ](j−1)/2 ≤ (1 2 )(j−1)/2 = 2−(j−1)/2 = 2−Ω(j), for j ≥ 1. Again, by Taylor's Theorem f(y) = f (y∞) + f ′ (y∞) (y − y∞) + 12f ′′ (v) (y − y∞)2, for some v ∈[y, y∞]. In our analysis of f ′, we show that f ′ (y∞) = 0, for ∆ ∈ (0, 2) (see Equation C.6). So the error term ξ+ (j + 1) = y∞ − f (yj) be
omes y∞ − f (y∞)− f ′ (y∞) (yj − y∞) − 12f ′′ (v) (yj − y∞)2 = −12f ′′ (v) (y − y∞)2 = −12f ′′ (v) ξ+ (j)2. Un- fortunately, f ′′ (v) may be poorly behaved. In parti
ular, it may de
rease without bound at an extreme of (y1, y∞) as ∆ tends to zero or two. Fortunately, we are able to use the input pre
ision measure m to push ∆ away zero and two (see Lemma C.6). This enables the weak bound of f ′′ (v) ∈ [ −2O(m), 0 ] (see Corollary C.7). Hen
e, ξ+ (j + 1) ≤ 2O(m)ξ+ (j)2. Earlier we showed that ξ (j) ≤ 2−Ω(j), for j ≥ 1. We use this rapid 
onvergen
e to take us into the domain where the bound ξ+ (j + 1) ≤ 2O(m)ξ+ (j)2 be
omes dominant. Consider j0 and d > 0 su
h that j ≥ j0 implies that ξ+ (j) ≤ 2−dj . Similarly, 
onsider m0 and c > 0 su
h that m ≥ m0 implies that ξ+ (j + 1) ≤ 2cmξ+ (j)2. Let h = max {⌈ cm+1 d ⌉ , j0 } = O (m). We now argue indu
tively that ξ+ (h+ i) ≤ 2−(cm+2i). The base 
ase is i = 0. Then ξ+ (h) ≤ 2−dh ≤ 2−d⌈ cm+1 d ⌉ ≤ 2−(cm+1). So suppose that ξ+ (h+ i) ≤ 2−(cm+2i). Then ξ+ (h+ (i+ 1)) ≤ 2cmξ+ (h+ i)2 ≤ 2cm [ 2−(cm+2 i) ]2 = 2cm [ 2−(2cm+2 i+1) ] = 2−(cm+2 i+1) . 89 It is now straightforward to prove that ξ+ (j) ≤ 2−2Ω(j) , for j > O(m). Consider any j > 2h = O (m). Let i = j − h = j 2 + ( j 2 − h ) ≥ h. Then ξ+ (j) = ξ+ (h + i) ≤ 2−(cm+2 i) ≤ 2−2i ≤ 2−2j/2 = 2−2Ω(j) . We now prove the 
laims used in the above theorem. Re
all that the rst and se
ond derivatives of f were 
ru
ial to our analysis by Taylor expansion. f ′ (y) = d dy [ 1 2 ( 2−∆ ( 1− y2 )1/2) y−1 ] by EquationC.1 = 1 2 [ y−1 d dy ( 2−∆ ( 1− y2 )1/2) + ( 2−∆ ( 1− y2 )1/2) d dy y−1 ] = 1 2 [ −∆y−1 d dy ( 1− y2 )1/2 − (2−∆ (1− y2)1/2) y−2 ] = 1 2 [ −∆ 2 y−1 ( 1− y2 )−1/2 d dy ( 1− y2 ) − ( 2−∆ ( 1− y2 )1/2) y−2 ] = 1 2 [ ∆ ( 1− y2 )−1/2 − (2−∆ (1− y2)1/2) y−2] = 1 2 [ ∆y2 ( 1− y2 )−1/2 − (2−∆ (1− y2)1/2)] y−2 = 1 2 [ ∆y2 ( 1− y2 )−1/2 +∆ ( 1− y2 )1/2 − 2] y−2 = 1 2 [ ∆y2 +∆ ( 1− y2 ) − 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2 = 1 2 [ ∆− 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2 (C.2) and f ′′ (y) = d dy ( 1 2 [ ∆− 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2) = 1 2   y−2 (1− y2)−1/2 d dy ( ∆− 2 (1− y2)1/2 ) +( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 d dy y−2+( ∆− 2 (1− y2)1/2 ) y−2 d dy (1− y2)−1/2   = 1 2   −y−2 (1− y2)−1/2 (1− y2)−1/2 d dy (1− y2)+ −2 ( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 y−3+ −1 2 ( ∆− 2 (1− y2)1/2 ) y−2 (1− y2)−3/2 d dy (1− y2)   = 1 2   2y−1 (1− y2)−1 − 2 ( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 y−3+( ∆− 2 (1− y2)1/2 ) y−1 (1− y2)−3/2   90 = 1 2   2y2 (1− y2)1/2 − 2 ( ∆− 2 (1− y2)1/2 ) (1− y2) + ( ∆− 2 (1− y2)1/2 ) y2   y−3 (1− y2)−3/2 = 1 2   2y2 (1− y2)1/2 − 2∆ (1− y2) + 4 (1− y2)3/2 +∆y2 − 2y2 (1− y2)1/2   y−3 (1− y2)−3/2 = 1 2 [ −2∆ + 2∆y2 + 4 ( 1− y2 )3/2 +∆y2 ] y−3 ( 1− y2 )−3/2 = 1 2 y−3 ( 1− y2 )−3/2 · g (y) where g (y) = 3∆y2 + 4 (1− y2)3/2 − 2∆ (C.3) The xed-point y∞ is essential be
ause iteration restri
ts f ′ and f ′′ to the domain (y1, y∞). y∞ = f (y∞) = 1 2 · ( 2−∆ √ 1− y2∞ ) y−1∞ y2∞ = 1− ∆ 2 √ 1− y2∞ 1− y2∞ = ∆ 2 √ 1− y2∞√ 1− y2∞ = ∆ 2 , assuming y∞ 6= −1, (i.e. ∆ 6= 0) 1− y2∞ = ∆2 4 y∞ = − √ 1− ∆ 2 4 (C.4) The restri
tion of the domain to (y1, y∞) produ
es a loose bound on f ′′ (y). Lemma C.4. The fun
tion f ′′ (y) is negative and the fun
tion g (y) is in (0,∆), for y ∈ (−1, y∞) and ∆ ∈ (0, 2]. Proof. We rst prove that g (y) ∈ (0,∆) by showing that g (y) is monotoni
ally de
reas- ing. Consider the derivative g′ (y) = 6∆y − 12y (1− y2)1/2 = 6y [ ∆− 2 (1− y2)1/2 ] . Now y < y∞ = − √ 1− ∆ 2 4 by EquationC.4 y2 > 1− ∆ 2 4 ∆2 4 > 1− y2 ∆ > 2 ( 1− y2 )1/2 91 So g′ (y) is negative, for y ∈ (−1, y∞). It follows by the Mean Value Theorem that g (y) ∈ (g (y∞) , g (−1)), for y ∈ (−1, y∞). Now g (y∞) = 3∆y 2 ∞ + 4 ( 1− y2∞ )3/2 − 2∆ = 3∆ ( 1− ∆ 2 4 ) + 4 ( 1− ( 1− ∆ 2 4 ))3/2 − 2∆ = 3∆− 3 4 ∆3 + 4 ( ∆2 4 )3/2 − 2∆ = 3∆− 3 4 ∆3 + 1 2 ∆3 − 2∆ = ∆− 1 4 ∆3 = 1 4 ∆ ( 4−∆2 ) = 1 4 ∆ (2 + ∆) (2−∆) ≥ 0, for ∆ ∈ (0, 2] g (−1) = 3∆ (−1)2 + 4 ( 1− [−1]2 )3/2 − 2∆ = 3∆− 2∆ = ∆ Hen
e g (y) ∈ (0,∆), for y ∈ (−1, y∞). Clearly, the fa
tor 12y−3 (1− y2) −3/2 of f ′′ (y) is negative for y ∈ (−1, 0) ⊃ (−1, y∞). Therefore, f ′′ (y) is negative, for y ∈ (−1, y∞). This loose bound on f ′′ is su
ient for a tight bound on f ′. Corollary C.5. The fun
tion f ′ (y) is in [ 0, 3 5 ] , for y ∈ [y1, y∞] and ∆ ∈ (0, 2]. Proof. We rst argue that f ′ (y) is 
ontinuous for y ∈ [−1, y∞]. By inspe
tion of Equation C.2, the potential dis
ontinuities of f ′(y) o

ur when y is −1 or 0. When y is −1, y1 must be −1, whi
h implies that ∆ is 0. So we 
an ignore this 
ase. When y is 0, y∞ must be 0, whi
h in turn implies that ∆ is 2. Let us evaluate f ′ (y) in this spe
ial 
ase. lim y→0 f ′ (y) = lim y→0 1 2 · 2− 2 (1− y 2) 1/2 y2 (1− y2)1/2 = 1 2 · 0 0 , whi
h is undened So we apply L'Hospital's Rule lim y→0 f ′(y) = lim y→0 1 2 · 2 (1− y 2) −1/2 y 2y (1− y2)1/2 − y3 (1− y2)−1/2 = lim y→0 1 2 · 2 2 (1− y2)− y2 = 1 2 · 2 2 = 1 2 Hen
e f ′ (y) is 
ontinuous on y ∈ [y1, y∞]. Therefore, f ′ (y) ∈ [f ′ (y∞) , f ′ (y1)], for y ∈ [y1, y∞] by the Mean Value Theorem and Lemma C.4. f ′ (y1) = 1 2 [ ∆− 2 ( 1− y21 )1/2] y−21 ( 1− y21 )−1/2 by EquationC.2 92 = 1 2 [ ∆− 2 ( 1− ( 1−∆2/9 ))1/2] ( 1−∆2/9 )−1 ( 1− ( 1−∆2/9 ))−1/2 by Figure 5.7(b) = 1 2 [ ∆− 2 ( ∆2/9 )1/2] ( 1−∆2/9 )−1 ( ∆2/9 )−1/2 = 1 2 [∆− 2∆/3] ( 1−∆2/9 )−1 (∆/3)−1 = 1 2 · ( 1−∆2/9 )−1 ≤ 1 3 (1− 4/9)−1 = 1 3 ( 5 9 )−1 = 3 5 (C.5) f ′ (y∞) = 1 2 [ ∆− 2 ( 1− y2∞ )1/2] y−2∞ ( 1− y2∞ )−1/2 by EquationC.2 = 1 2  ∆− 2 ( 1− [ 1− ∆ 2 4 ])1/2 ( 1− ∆ 2 4 )−1 ( 1− ( 1− ∆ 2 4 ))−1/2 by EquationC.4 = 1 2  ∆− 2 ( ∆2 4 )1/2 ( 1− ∆ 2 4 )−1 ( ∆2 4 )−1/2 = 1 2 (∆−∆) ( 1− ∆ 2 4 )−1 ( ∆ 2 )−1 = 0, for ∆ ∈ (0, 2) (C.6) We get a tighter bound on f ′′ (y) by pushing y from away from −1 and 0, where f ′′(y) 
ould degenerate. Lemma C.6. If ∆ ∈ (0, 2), then [y1, y∞] ⊆ [ 2−O(m) − 1,−2−O(m) ] . Proof. By Lemma C.1,∆ ∈ [ 2−O(m), 2− 2−O(m) ] . Hen
e, [y1, y∞] ⊆ [ 2−O(m) − 1,−2−O(m) ] . y1 = − √ 1−∆2/9 ≥ − √ 1−∆2/9 + (∆2/9)2 = − √ (1−∆2/9)2 = ∆2/9− 1 ≥ 2−O(m) − 1 To show that y∞ ≤ −2−O(m), we note that y∞ = − √ 1−∆2/4 is monotoni
ally in
reas- ing with values of ∆ in the range (0, 2). y∞ = −1 2 √ 4−∆2 = −1 2 √ 4− (2− 2−O(m))2 = −1 2 √ 4− (4− 4β + β2) = −1 2 √ 4β − β2 = −1 2 √ 2 · 2−O(m) − 2−2O(m) ≤ −1 2 93 Consider the 
hange of variables β = 2−∆. Then β ≥ 2−O(m) and y∞ is monoton- i
ally de
reasing with β. Now y∞ = −1 2 √ 4−∆2 = −1 2 √ 4− (2− β)2 = −1 2 √ 4− (4− 4β + β2) = −1 2 √ 4β − β2 If β ≥ 1, then y∞ = −12 √ β (4− β) ≤ −1 2 √ 4− β ≤ −1 2 √ 4− 2 = − √ 2 2 ≤ −2−O(1) = −2−O(m). If β ≤ 1, then β2 ≤ β and y∞ = −1 2 √ 4β − β2 ≤ −1 2 √ 4β − β = − √ 3 2 √ β = − √ 3 2 ( 2−O(m) )1/2 = −2−O(m) We 
an bound f ′′ using these bounds away from degenera
y. Corollary C.7. If ∆ ∈ (0, 2), then f ′′ (y) ∈ [ −2O(m), 0 ] , for y ∈ [y1, y∞]. We bound the fa
tor 1 2 y−3 (1− y2)−3/2of f ′′ (y) be
ause y ∈ [ 2−O(m) − 1,−2−O(m) ] ⊇ [y1, y∞]. Either y ≤ −1/ √ 2 or y ≥ −1/√2. Suppose the former. Then y ∈ [ 2−O(m) − 1,− 1√ 2 ] . Both y−3and (1− y2)−3/2 are monotoni
 in this domain, so we 
an bound them by evaluating them at the interval endpoints. Hen
e y−3 ∈ [( −√2 )3 , (−1)3 ] = [ −2√2,−1 ] . To evaluate (1− y2)−3/2 at 2−O(m)−1, suppose that y = 2−h(m)−1, where h(m) = O (m). Re
all that y ≤ 0, whi
h implies that h (m) > 0. Then ( 1− y2 )−3/2 = ( 1− ( 2−h(m) − 1 )2)−3/2 = ( 1− ( 2−2h(m) − 2 · 2−h(m) + 1 ))−3/2 = ( 2 · 2−h(m) − 2−2h(m) )−3/2 ≤ ( 2 · 2−h(m) − 2−h(m) )−3/2 by monotono
ity of z−3/2 on z ∈ (0,∞) = ( 2−h(m) )−3/2 = 2( 3 2 h(m)) So y = 2−O(m) − 1 implies that (1− y2)−3/2 = 2O(m). At the other interval endpoint. ( 1− y2 )−3/2 =  1− ( − 1√ 2 )2 −3/2 = ( 1− 1 2 )−3/2 = (2)3/2 = 2 √ 2 Therefore, 1 2 y−3 (1− y2)−3/2 ∈ [ 1 2 · ( −2√2 ) · 2O(m), 1 2 · (−1) · 2√2 ] ⊆ [ −2O(m),−√2 ] . 94 So suppose that y ≥ −1/√2. Then y ∈ [ − 1√ 2 ,−2−O(m) ] . Again, both y−3 and (1− y2)−3/2 are monotoni
 in this domain, so we 
an bound both by evaluating them at the interval endpoints. To evaluate y−3 at y = −2−O(m), let y = −2−h(m) , where h (m) = O (m). We require y ≥ −1, so h (m) ≥ 0. Then y−3 = ( −2−h(m) )−3 = − ( 2−h(m) )−3 = −23h(m) So y = −2−O(m) implies y−3 = −2O(m). Hen
e y−3 ∈ [ −2O(m),−2√2 ] . If y = 0 then (1− y2)−3/2 = 1. So (1− y2)−3/2 ∈ [ 1, 2 √ 2 ] . Therefore 1 2 y−3 ( 1− y2 )−3/2 ∈ [1 2 · ( −2O(m) ) · 2 √ 2, 1 2 · ( −2 √ 2 ) · 1 ] ⊆ [ −2O(m),− √ 2 ] Combined with our bound on g (y) ∈ (0,∆), we know that f ′′ (y) ∈ [ −2O(m), 0 ] . C.2 Forward Iteration (∆ > 2) dj cj cj+1 L T d∞ dj+1 H I (a) Constru
tion for ∆ = 2. dj cj cj+1 L T dj+1 H d∞ I (b) Constru
tion for ∆ > 2. Figure C.2: The position of L for ∆ > 2 is the same as its position for ∆ = 2. When the distan
e between 
orners is greater than two, we simplify our analysis by using the 
onstru
tion of the previous se
tion when the distan
e is exa
tly two (see Figures C.2(a)). This underestimate is valid be
ause cj+1 is on the appropriate side of T (see Figure C.2(b)). The quadrati
 
onvergen
e of the previous se
tion expli
itly required the distan
e between 
orner to be stri
tly less than two (see Theorem C.3). Fortunately, quadrati
 
onvergen
e to d∞ is unne
essary be
ause iterating to a window around d∞ 
overs the desired range. Re
all that we are trying to 
over the range of orientations in quadrant A (see Figure 5.6(a)). The underestimates from ba
kward iteration (i.e. d−1, d−2, . . .) 
over the horizontal orientation of quadrant A up to the orientations of d1. With forward iteration 95 df 1 α− 1 l h d∞ Figure C.3: Underlying 
ir
les with 
entres between df and d∞ rea
h the end of the range. (i.e. d1, d2, . . .), ea
h underestimate of dj+1 
overs a 
ontiguous range overlapping the previous underestimate of dj. So we have 
overed quadrant A on
e a bin 
overs the verti
al orientation of quadrant A. Ea
h bin 
orresponding to a dj on the dashed ar between df and d∞ in Figure C.3 has this property. We now argue that this ar
 is large. Lemma C.8. If ∆ > 2, then h = y∞ − yf ≥ 2−O(m). From Figure C.3, we see that l = √ (∆− 1)2 − 1 = √∆2 − 2∆. By 
ommon angles, the triangle with side lengths h and 1 is 
ongruent to the triangle with side lengths l and ∆− 1. So h = h 1 = l ∆− 1 = √ ∆2 − 2∆ ∆− 1 = ( ∆2 − 2∆ )1/2 (∆− 1)−1 We prove that h is monotoni
ally in
reasing with respe
t to ∆ by examining the derivative. h′ (∆) = (∆− 1)−1 d d∆ ( ∆2 − 2∆ )1/2 + ( ∆2 − 2∆ )1/2 d d∆ (∆− 1)−1 = (∆− 1)−1 · 1 2 ( ∆2 − 2∆ )−1/2 d d∆ ( ∆2 − 2∆ ) − ( ∆2 − 2∆ )1/2 (∆− 1)−2 d d∆ (∆− 1) = (∆− 1)−1 · 1 2 ( ∆2 − 2∆ )−1/2 (2∆− 2)− ( ∆2 − 2∆ )1/2 (∆− 1)−2 = ( ∆2 − 2∆ )−1/2 − (∆2 − 2∆)1/2 (∆− 1)−2 = ( ∆2 − 2∆ )−1/2 (∆− 1)2 (∆− 1)−2 − ( ∆2 − 2∆ )1/2 ( ∆2 − 2∆ )1/2 ( ∆2 − 2∆ )−1/2 (∆− 1)−2 = [ (∆− 1)2 − ( ∆2 − 2∆ )] ( ∆2 − 2∆ )−1/2 (∆− 1)−2 = [ ∆2 − 2∆ + 1− ( ∆2 − 2∆ )] ( ∆2 − 2∆ )−1/2 (∆− 1)−2 96 = ( ∆2 − 2∆ )−1/2 (∆− 1)−2 > 0, for ∆ > 2 by inspe
tion By the Mean Value Theorem, h is minimised as ∆ tends to 2 be
ause h is 
ontinuous, for ∆ ≥ 2. We 
an lower bound h by using the lower bound 2 + 2−O(m)on ∆ given by Lemma C.1. Suppose that ∆ = 2 + 2−g(m), where g (m) = O (m) ≥ 0. In this 
ase, h = ( ∆2 − 2∆ )1/2 (∆− 1)−1 = ([ 2 + 2−g(m) ]2 − 2 [2 + 2−g(m)])1/2 ([2 + 2−g(m)]− 1)−1 = ( 4 + 4 · 2−g(m) + 2−2g(m) − 4− 2 · 2−g(m) )1/2 ( 1 + 2−g(m) )−1 = ( 2 · 2−g(m) + 2−2g(m) ) ( 1 + 2−g(m) )−1 ≥ 2−g(m) ( 1 + 2−g(m) )−1 ≥ 2−g(m) (1 + 20)−1 = 2−g(m)2−1 = 2−[g(m)+1] So h ≥ 2−O(m). From Theorem C.3, ξ+ (j) = y∞ − yj ≤ 2−Ω(j), for j > 1. We just argued that we 
an stop iterating on
e y∞ − yj < y∞ − yf ≤ 2−O(m). This is guaranteed when 2−Ω(j) < 2−O(m), whi
h is equivalent to O (m) < Ω (j). So it is su
ient for j = O (m), and only O (m) bins are required. C.3 Ba
kward Iteration (∆ ≤ 2) dj cj L T H d−∞ cj−1dj−1 I Figure C.4: Underestimate of ba
kward iteration. Although the 
onstru
tions shown in either Figure 5.7(a) or C.1 dene mappings of dj to dj−1, we 
hoose an underestimate that is easier to analyse algebrai
ally (see Figure C.4): We ree
t dj through the line L of equidistan
e to get cj, we draw a line T through d−∞ and the midpoint of cj and dj, and let dj−1 be a point of interse
tion between H and T . If T were tangent to H , this would be the inverse of Figure C.1. 97 However, T interse
ts H twi
e, so it is a further underestimate. To see why we 
hose it, let y be the y-
oordinate of dj and f (y) be the y-
oordinate of dj−1. Then the slope of T 
an be expressed two ways. m = y + 1 ∆/2 = f (y) + 1√ 1− f (y)2 2 (y + 1) √ 1− f (y)2 = ∆(f (y) + 1) 4 (y + 1)2 ( 1− f (y)2 ) = ∆2 (f (y) + 1)2 4 (y + 1)2 (1− f (y)) (1 + f (y)) = ∆2 (f (y) + 1)2 4 (y + 1)2 (1− f (y)) = ∆2 (f (y) + 1) 4 (y + 1)2 − 4f (y) (y + 1)2 = ∆2f (y) + ∆2 4 (y + 1)2 −∆2 = ∆2f (y) + 4f (y) (y + 1)2 4 (y + 1)2 −∆2 = f (y) ( ∆2 + 4 (y + 1)2 ) f (y) = ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−1 Theorem C.9. The error measure ξ− (j) = y−j − y−∞ de
reases very rapidly. In parti
ular 1. If ∆ ∈ (0, 2], then ξ− (j) ≤ 2−Ω(j), for j > 1. 2. If ∆ ∈ (0, 2], then ξ− (j) ≤ 2−2Ω(j) , for j > O(m). As before, our error analysis fo
uses on the Taylor expansion of f (y) at the xed point y−∞. In parti
ular, f (y) = f (y−∞) + f ′ (u) (y − y−∞), for some u ∈ [y−∞, y]. Hen
e ξ− (j + 1) = f (y−j) − y−∞ = f ′ (u) (y−j − y−∞) = f ′ (u) ξ− (j). Corollary C.11 bounds f ′ (u) ∈ [ 0, 4 5 ] , for ∆ ∈ (0, 2]. Hen
e, ξ+ (j + 1) ≤ 45ξ− (j). Now ξ− (j) ≤ 1, so ξ− (j) ≤ ( 4 5 )j−1 = [( 4 5 )4](j−1)/4 = [ 256 625 ](j−1)/4 ≤ (1 2 )(j−1)/4 = 2−(j−1)/4 = 2−Ω(j), for j ≥ 1. Again, by Taylor's Theorem f(y) = f (y−∞)+f ′ (y−∞) (y − y−∞)+12f ′′ (v) (y − y−∞)2, for some v ∈[y−∞, y]. In our analysis of f ′, we show that f ′ (y−∞) = 0, for ∆ ∈ (0, 2] (see Equation C.7). So the error term ξ− (j + 1) = f (y−j) − y−∞ be
omes f (y−∞)+ f ′ (y−∞) (y−j − y−∞)+ 12f ′′ (v) (y−j − y−∞)2− y−∞ = 12f ′′ (v) (y−j − y−∞)2 = 1 2 f ′′ (v) ξ− (j) 2 . Unfortunately, f ′′ (v) may be poorly behaved. In parti
ular, it may de
rease without bound as v tends to y−∞ when ∆ tends to zero. Fortunately, we are able to use the input pre
ision measure m to push ∆ away zero (see Lemma C.1). This enables the weak bound of f ′′ (v) ∈ [ 0, 2O(m) ] (see Lemma C.12). Hen
e, ξ− (j + 1) ≤ 2O(m)ξ− (j) 2 . Earlier we showed that ξ− (j) ≤ 2−Ω(j), for j ≥ 1. We use this rapid 
onvergen
e to take us into the domain where the bound ξ− (j + 1) ≤ 2O(m)ξ− (j)2 be
omes dominant. 98 Consider j0 and d > 0 su
h that j ≥ j0 implies that ξ− (j) ≤ 2−dj . Similarly, 
onsider m0 and c > 0 su
h that m ≥ m0 implies that ξ− (j + 1) ≤ 2cmξ− (j)2. Let h = max {⌈ cm+1 d ⌉ , j0 } = O (m). We now argue indu
tively that ξ− (h+ i) ≤ 2−(cm+2i). The base 
ase is i = 0. Then ξ− (h) ≤ 2−dh ≤ 2−d⌈ cm+1 d ⌉ ≤ 2−(cm+1). So suppose that ξ− (h+ i) ≤ 2−(cm+2i). Then ξ− (h+ (i+ 1)) ≤ 2cmξ− (h+ i)2 ≤ 2cm [ 2−(cm+2 i) ]2 = 2cm [ 2−(2cm+2 i+1) ] = 2−(cm+2 i+1) . It is now straightforward to prove that ξ− (j) ≤ 2−2Ω(j) , for j > O(m). Consider any j > 2h = O (m). Let i = j − h = j 2 + ( j 2 − h ) ≥ h. Then ξ− (j) = ξ− (h + i) ≤ 2−(cm+2 i) ≤ 2−2i ≤ 2−2j/2 = 2−2Ω(j) . The above proof used Taylor expansions of f (y) in terms of f ′ (y) and f ′′ (y) . f ′ (y) = d dy ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−1 = ( 4 (y + 1)2 −∆2 ) d dy ( 4 (y + 1)2 +∆2 )−1 + ( 4 (y + 1)2 +∆2 )−1 d dy ( 4 (y + 1)2 −∆2 ) = ( 4 (y + 1)2 −∆2 ) · −1 · ( 4 (y + 1)2 +∆2 )−2 d dy ( 4 (y + 1)2 +∆2 ) + ( 4 (y + 1)2 +∆2 )−1 · 8 · (y + 1) = − ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−2 · 8 · (y + 1) + ( 4 (y + 1)2 +∆2 )−1 · 8 · (y + 1) = 8 · (y + 1) [( 4 (y + 1)2 +∆2 )−1 − (4 (y + 1)2 −∆2) (4 (y + 1)2 +∆2)−2] = 8 (y + 1) ( 4 (y + 1)2 +∆2 )−2 [( 4 (y + 1)2 +∆2 ) − ( 4 (y + 1)2 −∆2 )] = 16∆2 (y + 1) ( 4 (y + 1)2 +∆2 )−2 f ′′ (y) = d dy [ 16∆2 (y + 1) ( 4 (y + 1)2 +∆2 )−2] = 16∆2 d dy [ (y + 1) ( 4 (y + 1)2 +∆2 )−2] = 16∆2   (y + 1) ddy ( 4 (y + 1)2 +∆2 )−2 + ( 4 (y + 1)2 +∆2 )−2 d dy (y + 1)   99 = 16∆2   (y + 1) · −2 · ( 4 (y + 1)2 +∆2 )−3 d dy ( 4 (y + 1)2 +∆2 ) + ( 4 (y + 1)2 +∆2 )−2   = 16∆2 [ −2 (y + 1) ( 4 (y + 1)2 +∆2 )−3 · 8 · (y + 1) + (4 (y + 1)2 +∆2)−2] = 16∆2 [ −16 (y + 1)2 ( 4 (y + 1)2 +∆2 )−3 + ( 4 (y + 1)2 +∆2 )−2] = 16∆2 ( 4 (y + 1)2 +∆2 )−3 [( 4 (y + 1)2 +∆2 ) − 16 (y + 1)2 ] = 16∆2 ( ∆2 − 12 (y + 1)2 ) ( 4 (y + 1)2 +∆2 )−3 In order to bound f ′ (y), we show that it is monotoni
ally in
reasing on its domain. Lemma C.10. The se
ond derivative f ′′ (y) is positive, for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. The sign of f ′′ (y) 
hanges at 12 (y + 1)2 = ∆2 y + 1 = ± ∆√ 12 y = ± ∆√ 12 − 1 Re
all that y ∈ [y−∞, y−1]. We note that −1−∆/ √ 12 < y−∞ be
ause ∆ > 0. We now show that y−1 = − √ 1− (∆/5)2 < ∆/ √ 12− 1√ 1− (∆/5)2 > 1−∆/ √ 12 1− (∆/5)2 > 1− 2∆/ √ 12 + ∆2/12 2∆/ √ 12 > ∆2/12 + ∆2/25 2/ √ 12 > ∆(1/12 + 1/25) 2/ √ 12 > ∆(37/300) ∆ < 600/ ( 37 √ 12 ) = 50 √ 12/37 Now 50 √ 12/37 ≥ 50√9/37 = 150/37 > 2. Therefore f ′′(y) > 0, for y ∈ [y−∞, y−1]. Corollary C.11. The rst derivative f ′ (y) is in [0, 4/5], for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. By inspe
tion, f ′ (y) is 
ontinuous on y ∈ [−1, 0] ⊇ [y−∞, y−1] be
ause ∆ > 0. Hen
e f ′ (y) ∈ [f ′ (y−∞) , f ′ (y−1)] by the Mean Value Theorem and Lemma C.10. Then 100 f ′ (y−∞) = 16∆ 2 ((−1) + 1) ( 4 (−1 + 1)2 +∆2 )−2 = 16∆2 · 0 ·∆−4 = 0, for ∆ ∈ (0, 2] (C.7) The interval end-point is harder to evaluate be
ause f ′ (y−1) is a 
omposition of two fun
tions, f ′ (y) and y−1, with a dependen
e on ∆. We analyse this 
omposition using the Chain Rule df ′(y−1) d∆ = df ′(y−1) dy−1 · dy−1 d∆ . By Lemma C.10, the rst fa
tor is positive, for ∆ ∈ (0, 2]. We now derive the se
ond fa
tor. y−1 (∆) = − (1− (∆/5))1/2 dy−1 d∆ = − d d∆ ( 1− (∆/5)2 )1/2 = −1 2 ( 1− (∆/5)2 )−1/2 · d d∆ ( 1− (∆/5)2 ) = −1 2 ( 1− (∆/5)2 )−1/2 · −2 (∆/5) = (∆/5) ( 1− (∆/5)2 )−1/2 = ∆ ( 5−∆2 )−1/2 > 0, for ∆ ∈ (0, 2] So, df ′(y−1) d∆ is positive for ∆ ∈ (0, 2]. The 
omposition of 
ontinuous fun
tions is 
ontinuous, so f ′ (y−1 (∆)) is 
ontinuous on ∆ ∈ (0, 2] be
ause f ′ (y) is 
ontinuous on y ∈ [−1, 0] and y−1 (∆) is 
ontinuous on ∆ ∈ (0, 2]. Therefore f ′ (y−1 (∆)) ∈ [f ′ (y−1 (0)) , f ′ (y−1 (2))] by the Mean Value Theorem. Now f ′ (y) is non-negative by inspe
tion, so f ′ (y−1 (0)) ≥ 0. y−1 (2) = − ( 1− (2/5)2 )1/2 = − (1− 4/25)1/2 = − (21/25)1/2 ≤ −4/5 f ′ (y−1 (2)) = 16 · 22 · (y−1 (2) + 1) ( 4 (y−1 (2) + 1) 2 + 22 )−2 ≤ 16 · 4 · ( −4 5 + 1 ) ( 0 + 22 )−2 = 16 · 4 · 1 5 · 1 16 = 4 5 Thus f ′ (y−1 (∆)) ∈ [0, 4/5], for∆ ∈ (0, 2]. Therefore, f ′ (y) ∈ [0, 4/5] ⊇ [f ′ (y−∞) , f ′ (y−1)], for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. To get a tighter bound on f ′′ (y), we use a bound pushing ∆ away from 0 (see Lemma C.1). Lemma C.12. The se
ond derivative f ′′ (y) is in [ 0, 2O(m) ] , for y ∈ [y−1, y−∞] and ∆ ∈ (0, 2]. Lemma C.10 asserts that f ′′ (y) ≥ 0. Now we derive an upper bound. f ′′ (v) = 16∆2 ( ∆2 − 12 (v + 1)2 ) ( 4 (v + 1)2 +∆2 )−3 ≤ 16∆2 ( ∆2 − 0 ) ( 0 + ∆2 )−3 = 16∆2 ·∆2 ·∆−6 = 16∆−2 101 Therefore, f ′′ (y) ∈ [0, 16∆−2]. By Lemma C.1, ∆ > 2−O(m). Hen
e f ′′ (y) ∈ [ 0, 2O(m) ] . C.4 Ba
kward Iteration(∆ ≥ 2) dj cj cj+1 L T d−∞ dj+1 H I (a) Constru
tion for ∆ = 2. dj cj cj+1 L T dj+1 H d−∞ I (b) Constru
tion for ∆ > 2. Figure C.5: The position of L for ∆ > 2 is the same as its position for ∆ = 2. When the distan
e between 
orners is greater than two, we simplify our analysis by using the 
onstru
tion of the previous se
tion when the distan
e is exa
tly two (see Figures C.5(a)). This underestimate is valid be
ause cj+1 is on the appropriate side of T (see Figure C.5(b)). So we reuse the 
onvergen
e analysis of the previous se
tion (see Theorem C.9). 102

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0051257/manifest

Comment

Related Items