Sampling-based bottleneck pathfinding with applications to Fr ́ echet matching   ∗  Kiril Solovey   Dan Halperin  Blavatnik School of Computer Science, Tel Aviv University, Israel  Abstract  We describe a general probabilistic framework to address a variety of Fr ́ echet- distance optimization problems. Specifically, we are interested in finding minimal  bottleneck -paths in   d -dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimen- sions. Finally, we provide experimental results of the framework on several types of problems.  1   Introduction  This paper studies the problem of finding near-optimal paths in   d -dimensional Eu- clidean space. Specifically, we are interested in   bottleneck   paths which minimize the maximal value the path obtains over a generally-defined continuous cost map.   As an example, suppose that one wishes to plan a hiking route in a mountainous region between two camping grounds, such that the highest altitude along the path is mini- mized [17]. In this case, the map assigns to each two-dimensional point its altitude. A similar setting, albeit much more complex, requires to find a pathway of low energy for a given protein molecule (see, e.g., [37]). Our main motivation for studying bottleneck optimization over cost maps is its tight relation to the Fr ́ echet distance (or matching), which is a popular and widely studied similarity measure in computational geometry. The problem has applications to vari- ous domains such as path simplification [19], protein alignment [27], handwritten-text search [48], and signature verification [53]. The Fr ́ echet distance, which was initially defined for curves, is often considered to be a more informative measure than the pop- ular   Hausdorff   distance as it takes into consideration not only each curve as a whole but also the location and the ordering of points along it. Usually one is interested not only in the Fr ́ echet distance between two given curves, but also in the parametrization which attains the optimal alignment.  ∗ This work has been supported in part by the Israel Science Foundation (grant no. 1102/11), by the Blavatnik Computer Science Research Fund, and by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University. Kiril Solovey is also supported by the Clore Israel Foundation.  arXiv:1607.02770v1 [cs.CG] 10 Jul 2016
Since its introduction by Alt and Godau [2] in 1995, a vast number of works has been devoted to the subject, and many algorithms have been developed to tackle various settings of the problem. However, from a practical standpoint the problem is far from being solved: for many natural extensions of the Fr ́ echet problem only prohibitively- costly algorithms are known. Furthermore, in some cases it was shown, via hardness proofs, that efforts for finding polynomial-time algorithms are doomed to fail.   For some variants of the problem efficient algorithms are known to exist, however their implementation requires complex geometric machinery that relies on geometric kernels with infinite precision [30].  Contribution.   We describe a generic, efficient and simple algorithmic framework for solving pathfinding optimization problems over cost maps. The framework is in- spired by, and draws ideas from, sampling-based methods for robot motion planning. We provide experimental results of the framework on various scenarios. Furthermore, we theoretically analyze the framework and show that the cost of the obtained solution converges to the optimum, as the number of samples increases. We also consider the more demanding case, where paths need to be monotone in all dimensions.  Organization.   In Section 2 we review related work. In Section 3 we provide a formal definition of the bottleneck pathfinding problem. In Section 4 we describe an algorithmic framework for solving this problem. In Section 5 we provide an analysis of the method. Finally, in Section 6 we report on experimental results.  2   Related work  This section is devoted to related work on Fr ́ echet distance and robot motion planning.  2.1   Fr ́ echet distance  The   Fr ́ echet distance   between two curves is often described by an analogy to a person walking her dog: each of the two creatures is required to walk along a predefined path and the person wishes to know the length of the shortest   leash   which will make this walk possible. In many cases one also likes to know how to advance along the path given the short leash. Formally, let   σ 1 , σ 2   : [0 ,   1]   →   R d   be two continuous curves. We wish to find a traversal along the two curves which minimizes the distance between the two traversal points. The traversal is defined by two continuous parametrizations   α 1 , α 2   : [0 ,   1]   →  [0 ,   1]   of   σ 1 , σ 2   respectively, where for a given point in time   τ   ∈   [0 ,   1] , the positions of the person and her dog are specified by   σ 1 ( α 1 ( τ   ))   and   σ 2 ( α 2 ( τ   )) , respectively. The  Fr ́ echet distance   between   σ 1 , σ 2   is defined by the expression  min  α 1 ,α 2 :[0 , 1] → [0 , 1]   max  τ   ∈ [0 , 1]   ‖ σ 1 ( α 1 ( τ   ))   −   σ 2 ( α 2 ( τ   )) ‖ 2 .  Alt and Godau [2] described an   O ( n 2   log   n ) -time algorithm for the setting of two polygonal curves, where   n   is the number of vertices in each of the two curve. Buchin et al. [12] described a different method for solving this problem for the same running time. Recently, Buchin et al. [10] developed an algorithm with a slightly improved running time   O ( n 2   log 2   log   n ) . Har-Peled and Raichel [22] introduced a simpler randomized algorithm with running time of   O ( n 2   log   n ) . Bringmann [6] showed that an algorithm
with running time of   O ( n 2 − δ   ) , for some constant   δ >   0 , does not exist, unless a widely accepted conjecture, termed SETH [25], is wrong.   In a following work [7] this conditional lower bound was extended to   (1 +   ε ) -approximation algorithms of the Fr ́ echet problem, where   ε   ≤   0 . 399 . The notion of Fr ́ echet distance can be extended to   k   curves in various ways. One natural extension can be described figuratively as having a pack of   k   dogs, where each of the dogs has to walk along a predefined path, and every pair of dogs is connected with a leash. The goal now is to find a parametrization which minimizes the length of the longest leash. Dumitrescu and Rote [18] introduced a generalization of the Alt- Godau algorithm to this case, which runs in   O ( kn k   log   n )   time, i.e., exponential in the number of input curves. They also describe a   2 -approximation algorithm with a much lower running time of   O ( k 2 n 2   log   n ) . In the work of Har-Peled and Raichel [22] mentioned above they also consider the case of   k   input curves and devise an   O ( n k )  algorithm. Notably, their technique is flexible enough to cope with different Fr ́ echet- type goal functions over the   k   curves. Furthermore, their algorithm is also applicable when the   k   curves are replaced with   k   simplicial complexes , and the problem is to find  k   curves—one in each complex—which minimize the given goal function. A recent work [9], which extends the conditional lower bound mentioned earlier for the setting of multiple curves, suggests that a running time that is exponential in the number of curves is unavoidable. The notion of Fr ́ echet distance can be generalized to more complex objects. Buchin et al. [13] considered the problem of finding a mapping between two simple polygons, which minimizes the maximal distance between a point and its image in the other polygon. More formally, given two simple polygons   P, Q   ⊂   R 2   the problem consists of finding a mapping   δ   :   P   →   Q   which minimizes the expression   max p ∈ P   ‖ p − δ ( p ) ‖ 2 , subject to various constraints on   δ . They introduced a polynomial-time algorithm for this case. In a different paper, Buchin et al. [11] showed that the decision problem is  NP -hard for more complex geometric objects, e.g., pairs of polygons with holes in the plane or pairs of two-dimensional terrains. Another interesting   NP -hard problem that was studied by Sherette and Wenk [41] is   curve embedding   in which one wishes to find an embedding of a curve in   R 3   to a given plane, which minimizes the Fr ́ echet distance with the curve. In a similar setting Meulemans [34] showed that it is   NP -hard to decide whether there exists a simple cycle in a plane-embedded graph that has at most a given Fr ́ echet distance to a simple closed curve. The Fr ́ echet distance between curves in the presence of obstacles have earned some attention. Cook and Wenk [16] studied the   geodesic   variant, which consists of a simple polygon and two polygonal curves inside it. As in the standard formulation, the main goal is to minimize the length of the leash, but now the leash may wrap or bend around obstacles. Their algorithm has running time of   O ( m + n 2   log   mn   log   n ) , where   m   is the complexity of the polygon and   n   is defined as the total complexity of the two curves, as before. The more complex   homotopic   setting is a special case of the aforementioned geodesic setting, with the additional constraint that the leash must continuously deform. Chambers et al. [14] considered this problem for the specific setting of two curves in planar environment with polygonal obstacles.   They developed an algorithm whose running time is   O ( N   9   log   N   ) , where   N   =   n   +   m   for   n   and   m   as defined above.  2.2   Motion planning  Motion planning is a fundamental problem in robotics. In its most basic form, the prob- lem consists of finding a collision-free path for a robot   R   in a workspace environment
W   cluttered with obstacles. Typically, the problem is approached from the configu- ration space   C —the set of all robot configurations. The problem can be reformulated as finding a continuous curve in   C , which entirely consists of collision-free configu- rations and represents a path for the robot from a given start configuration to another, target, configuration. An important attribute of the problem is the number of   degrees of freedom   of   R , using which one can specify every configuration in   C . Typically the dimension of   C   equals the number of degrees of freedom. For some cases of the problem, which involve a small number of degrees of free- dom, efficient and exact analytical techniques exist (see, e.g.,   [4, 21, 40]), which are guaranteed to find a solution if one exists, or report that none exists otherwise. Re- cently, it was shown [1, 46, 50] that efficient and complete techniques can be developed for the   multi-robot   motion-planning problem, which entails many degrees of freedom, by making several simplifying assumptions on the separation of the start and target po- sitions. However, it is known that the general setting of the motion-planning problem is computationally intractable (see, e.g., [23, 38, 43, 47]) with respect to the number of degrees of freedom. Sampling-based algorithms for motion planning, which were first described about two decades ago, have revolutionized the field of robotics by providing simple yet effective tools to cope with challenging problems involving many degrees of free- dom.   Such algorithms (see, e.g., PRM by Kavraki et al. [29], RRT by Kuffner and LaValle [32], and EST by Hsu et al. [24]) explore the high-dimensional configuration space by random sampling and connecting nearby samples, which result in a graph data structure that can be viewed as an approximation of the   free space —a subspace of   C , which consists entirely of collision-free configurations. While such techniques have weaker theoretical guarantees than analytical methods, many of them are   prob- abilistically complete , i.e., guaranteed to find a solution if one exists, given sufficient processing time.   More recently,   asymptotically optimal   sampling-based algorithms, whose solution converges to the optimum, for various criteria, have started to emerge: Karaman and Frazzoli introduced the RRT* and PRM* [28] algorithms, which are asymptotically optimal variants of RRT and PRM. Following their footsteps Arslan and Tsiotras introduced RRT# [3].   A different approach was taken by Janson and Pavone who introduced the FMT* algorithm [26], which was later refined by Salzman and Halperin [39].  3   Problem statement  In this section we describe the general problem of bottleneck pathfinding over a given cost map, to which we describe an algorithmic framework in Section 4. We conclude this section we several concrete examples of the problems that will be used for experi- ments in Section 6. We start with several basic definitions. Given   x, y   ∈   R d , for some fixed dimension  d   ≥   2 , let   ‖ x   −   y ‖ 2   denote the Euclidean distance between two points. Denote by  B r   ( x )   the   d -dimensional Euclidean ball of radius   r >   0   centered at   x   ∈   R d   and  B r   (Γ) =   ⋃  x ∈ Γ   B r   ( x )   for any   Γ   ⊆   R d .   We will use the terms “path” and “curve” interchangeably, to refer to a continuous curve in   R d   parametrized over   [0 ,   1] . Given a curve   σ   : [0 ,   1]   →   R d   define   B r   ( σ ) =   ⋃  τ   ∈ [0 , 1]   B r   ( σ ( τ   )) . Additionally, denote the image of a curve   σ   by Im ( σ ) =   ⋃  τ   ∈ [0 , 1] { σ ( τ   ) } . Let   A 1 , A 2 , . . .   be random variables in some probability space and let   B   be an event depending on   A n .   We say that   B  occurs   almost surely   (a.s., in short) if   lim n →∞   Pr[ B ( A n )] = 1 .
Let   M   : [0 ,   1] d   →   R   be a   cost map   that assigns to each point in   [0 ,   1] d   a real value. For simplicity, we assume that the domain of   M   is a   d -dimensional unit hypercube. Let   S, T   ∈   [0 ,   1] d   denote the start and target points. Denote by   Σ( S, T   )   the collection of paths that start in   S   and end in   T   . Formally, every   σ   ∈   Σ( S, T   )   is a continuous path  σ   : [0 ,   1]   →   [0 ,   1] d , where   σ (0) =   S, σ (1) =   T   . Given a path   σ   we use the notation  M ( σ ) = max τ   ∈ [0 , 1]   M ( σ ( τ   ))   to represent its bottleneck cost. In some applications, monotone paths are desired.   For instance, in the classical problem of Fr ́ echet matching between two curves it is often the case that backward motion along the curves is forbidden.   Here we consider monotonicity in all   d   co- ordinates of points along the path.   Formally, given two points   p, p ′   ∈   R d , where  p   = ( p 1 , . . . , p d ) , p ′   = ( p ′  1 , . . . , p ′  d ) , we use the notation   p      p ′   to indicate that  p i   ≤   p ′  i , for every   1   ≤   i   ≤   d .   A path   σ   ∈   Σ( S, T   )   is said to be   monotone   if for every   0   ≤   τ   ≤   τ   ′   ≤   1   it holds that   σ ( τ   )      σ ( τ   ′ ) .  Definition 1.   Given the triplet   〈M , S, T   〉 , the   bottleneck-pathfinding problem   (BPP, for short) consists of finding a path   σ   ∈   Σ( S, T   )   which minimizes the expression  max τ   ∈ [0 , 1]   M ( σ ( τ   )) .   A special case of the bottleneck pathfinding problem, termed  strong -BPP, requires that the path will be   monotone .  3.1   Examples  We provide three examples of BPPs, which will be used for experiments in Section 6. Each example is paired with the   d -dimensional configuration space   C   := [0 ,   1] d , start and target points   S, T   ∈ C , and a cost map   M   : [0 ,   1] d   →   R . The examples below are defined for two-dimensional input objects, but can generalized to higher dimensions.  Problem 1:   We start with the classical   Fr ́ echet distance among   k   curves   (see, e.g., [22]).   Let   σ 1 , . . . , σ k   : [0 ,   1]   →   [0 ,   1] 2   be   k   continuous curves embedded in Euclidean plane. Here   C   = [0 ,   1] k   is defined as the Cartesian product of the various positions along the   k   curves. Namely, a point   P   = ( p 1 , . . . , p k )   ∈ C   describes the location   σ i ( p i )   along   σ i , for each   1   ≤   i   ≤   k . To every such   P   we assign the cost  M ( P   ) = max 1 ≤ i<j ≤ k   ‖ σ i ( p i )   −   σ j   ( p j   ) ‖ 2 . We note that more complex formulations of   M   can be used, depending on the exact application. The start and target positions are defined to be   S   = ( σ 1 (0) , . . . , σ k (0)) , T   = ( σ 1 (1) , . . . , σ k (2)) .  Problem 2:   We introduce the problem of   Fr ́ echet distance with visibility , whose basis is similar to   P1   with   k   = 3 . In addition to the curves, we are given a subspace  F ⊆   [0 ,   1] 2 . The goal is to find a traversal of the curves which minimizes   M   as defined in   P1 , with the additional constraint that the traversal point along   σ 1   must be “seen” by one of the traversal points of   σ 2 , σ 3 . Formally, for every   P   = ( p 1 , p 2 , p 3 )   ∈ C   it must hold that   p 1 p 2   ⊂ F   or   p 1 p 3   ⊂ F   (but not necessarily both), where   p i p j   is the straight-line path from   p i   to   p j   .  Problem 3:   In   curve embedding   (see, [34, 41]), the input consists of a curve  σ   : [0 ,   1]   →   [0 ,   1] 2 , a subspace   F   ⊆   [0 ,   1] 2   and a pair of two-dimensional points  s, t   ∈ F . A point   P   = ( p 1 , p 2 , p 3 )   ∈ C   = [0 ,   1] 3   describes the location   σ ( p 1 )   along  σ   and the point   ( p 2 , p 3 )   ∈ F . The BPP is defined for the start and target points   S   = (0 , s ) , T   = (1 , t )   ∈ C   and the cost map   M ( P   ) =   ‖ σ ( p 1 )   −   ( p 2 , p 3 ) ‖ 2 .
4   Algorithmic framework  In this section we describe an algorithmic framework that will be used for solving standard and strong regimes of BPP (Definition 1). The framework can be viewed as a variant of the PRM algorithm [28], and we chose to describe it here in full detail for completeness. However, the analysis provided in Section 5 is brand new. The framework consists of three conceptually simple steps: In the first step, we construct a random graph embedded in   [0 ,   1] d , whose vertices consist of the start and target points   S, T   , and of a collection of randomly sampled points; the edges connect points that are separated by a distance of at most a given connection threshold   r n . In the second step the edges of the graph are assigned with weights corresponding to their bottleneck cost over   M . In the third and final step, the discrete graph is searched for a path connecting   S   to   T   which minimizes the bottleneck cost. Before proceeding to a more elaborate description of the framework we provide a formal definition of the random graphs that are at the heart of the technique.   Let  X n   =   { X 1 , . . . , X n }   be   n   points chosen independently and uniformly at random from the Euclidean   d -dimensional cube   [0 ,   1] d . The following definition corresponds to the standard and well-studied model of random geometric graphs (see, e.g., [5, 36, 51] and the literature review in [45]).  Definition 2.   The   random geometric graph   (RGG)   G n   =   G ( X n ;   r n )   is a   directed   graph with vertex set   X n   and edge set   { ( x, y ) :   x   6   =   y, x, y   ∈ X n ,   ‖ x   −   y ‖ 2   ≤   r n } . We are ready to describe the framework, which has two parameters:   n   represents the number of samples generated and   r n   defines the Euclidean connection radius used in the construction of the graphs.   In the next section we show that for a range of values of   r n , which is a function of the number of samples   n , the cost of the returned solution converges to the optimum, as   n   tends to infinity. The framework consists of the following steps:  Step I:   We construct the RGG   G n   = ( X n   ∪ { S, T   } ;   r n ) . For the purpose of gen- erating   G n   a collection of   n   samples   X n   is generated and a nearest-neighbor structure is employed to find for every   x   ∈ X n   ∪ { S, T   }   the set of samples that located within a Euclidean distance of   r n   from it.  Step II:   We assign to each edge of the graph the bottleneck cost of the straight- line path connecting its endpoints under   M . In particular, for the standard BPP, for every edge   ( x, y )   the cost   max τ   ∈ [0 , 1]   M ( x   +   τ   ( y   −   x ))   is assigned. The same applies for strong-BPP, unless   x   6      y , in which case the value   + ∞   is assigned.  Step III:   For the final step we find a path over   G n   from   S   to   T   which mini- mizes the bottleneck cost. Several efficient algorithms solving this problem exist (see, e.g., [15, 52]).  5   Theoretical foundations  We study the behavior of the framework for the standard and the strong case of BPP (Definition 1). Recall the framework uses the two parameters   n   and   r n , which specify the number of samples and the connection radius.We establish a range of connection
radii,   r n , for which the cost of the returned solution is guaranteed to converge to a relaxed notion of the optimum. The analysis below does not restrict itself to a specific type of cost maps   M , e.g., continuous or smooth. Thus, due to the stochastic nature of the framework, and the general definition of   M , we cannot guarantee that the returned solution will tend to the absolute optimum. As an example consider the cost map   M   such that for a given  x   = ( x 1 , x 2 ) ,   M ( x ) = 0   if   x 1   =   x 2 , and   M ( x ) = 1   otherwise. For the start and target points   S   = (0 . 1 ,   0 . 1) , T   = (0 . 9 ,   0 . 9)   the optimal solution is a subset of the diagonal. Obviously, the probability of having a single point of   X n , let alone a whole path in   G n , that lie on the diagonal is equal to   0 . We can however guarantee convergence to a   robustly-optimal   path, which is defined below.   Informally, such paths have “well-behaved” neighborhoods, in terms of the value of   M . We provide below a formal definition of this notion for the bottleneck cost function. Recall that given a path   σ   the notation   M ( σ )   represents its bottleneck cost.  Definition 3.   Given the triplet   〈M , S, T   〉 , a path   σ   ∈   Σ( S, T   )   is called   robust   if for every   ε >   0   there exists   δ >   0   such that   M ( σ ′ )   ≤   (1 +   ε ) M ( σ ) , for any   σ ′   ∈   Σ( S, T   )  such that Im ( σ ′ )   ⊂ B δ   ( σ ) . A path that attains the infimum cost, over all robust paths, is termed   robustly optimal .  5.1   (Standard) Bottleneck cost  For a given triplet   〈M , S, T   〉   representing an instance of BPP, denote by   σ ∗   a robustly- optimal solution. Note that we do not require here that   σ ∗   or the returned solution will be monotone. We obtain the following result. All logarithms stated henceforth are to base   e .  Theorem 1.   Let   G n   =   G ( X n   ∪ { S, T   } ;   r n )   be an RGG with  r n   =   γ  (   log   n n  ) 1 /d  ,   γ >   2(2 dθ d ) − 1 /d ,  where   θ d   denotes the Lebesgue measure of a unit ball in   R d . Then   G n   contains a path  σ n   ∈   Σ( S, T   )   such that   M ( σ n ) = (1 +   o (1)) M ( σ ∗ ) , a.s.  We mention that this connection radius is also essential for connectivity of RGGs, i.e., a smaller radius results in a graph that is disconnected with high probability (see, e.g.,[8]). This fact is instrumental to our proof. We also mention that a result similar to Theorem 1 can be obtained through a different proof technique [28], albeit with a larger value of the constant   γ . For simplicity, we assume for the purpose of the proof that exists a finite constant  δ ′   >   0   such that   B δ ′   ( σ ∗ )   ⊂   [0 ,   1] d , namely the robustly-optimal solution is at least   δ ′  away from the boundary of the domain   [0 ,   1] d . This constraint can be easily relaxed by transforming   〈M , S, T   〉   into an equivalent instance   〈M ′ , S ′ , T   ′ 〉   where this condition is met. In particular the original input can be embedded to a cube of side length   1   −   ε  for some constant   ε >   0 , which is centered in the middle of   [0 ,   1] d . The cost along the boundaries of the smaller cube should be extended to the remaining parts of the   [0 ,   1] d  cube. Given an RGG   G n   and a subset   Γ   ⊂   [0 ,   1] d   denote by   G n (Γ)   the graph obtained from the intersection of   G n   and   Γ : it consists of the vertices of   G n   that are contained in
Γ   and the subset of edges of   G n   that are fully contained in   Γ . Each edge is considered as a straight-line segment connecting its two end points. A main ingredient in the proof of Theorem 1 is the following Lemma. We employ the   localization-tessellation   framework [45], which was developed by the authors. The framework allows to extend properties of RGGs to domains with complex geometry and topology.  Lemma 1.   Let   G n   be the RGG defined in Theorem 1.   Additionally let   Γ   ⊂   [0 ,   1] d  be a fixed subset, where   S, T   ∈   Γ , and let   ρ >   0   be some fixed constant, such that  B ρ (Γ)   ⊂   [0 ,   1] d . Then   S, T   are connected in   G n ( B ρ (Γ))   a.s. Proof.   We rely on the well-known result that   G n   is connected a.s. in the domain   [0 ,   1] d  for the given connection radius   r n   (see, e.g., [45, Theorem 1]). We then use Lemma 1 and Theorem 6 in [45] which state that if   G n   is connected a.s., and is   localizable   (see, Definition 6 therein), then   S, T   are connected a.s. over   G n ( B ρ (Γ)) .  Proof of Theorem 1.   We first show that for any   ε >   0   it follows that   M ( σ n )   ≤   (1 +  ε ) M ( σ ∗ )   a.s. Fix some   ε >   0 . Due to the fact that   σ ∗   is robustly optimal, there exists  δ ε   >   0   independent of   n   such that for every   σ   ∈   Σ( S, T   )   such that Im ( σ )   ⊂ B δ ε   ( σ ∗ )  we have that   M ≤   (1+ ε ) M ( σ ∗ )   a.s. Additionally, recall that there exists some   δ ′   >   0  such   B δ ′   ( σ ∗ )   ⊂   [0 ,   1] d . Set   δ   = min { δ ε , δ ′ }   and define the sets   Γ δ/ 2   =   B δ/ 2 ( σ ∗ ) ,   Γ δ   =   B δ   ( σ ∗ )   and notice that   S, T   ∈   Γ δ/ 2 . By Lemma 1 we have that   S, T   are connected in   G n (Γ δ   ) . Moreover, a path connecting   S, T   in   G n (Γ δ   )   must a have a bottleneck cost of at most   (1+ ε ) M ( σ ∗ ) . We have shown that for any fixed   ε >   0 ,   M ( σ n )   ≤   (1 +   ε ) M ( σ ∗ )   a.s. By defining the sequence   ε i   = 1 /i   one can extend the previous result and show that   M ( σ n )   ≤  (1 +   o (1)) M ( σ ∗ ) . This part is technical and its details are omitted (see a similar proof in [44, Theorem 6]). This concludes the proof.  5.2   Strong bottleneck cost  We now focus on the strong case of the problem, where the solution is restricted to paths that are monotone in each of the   d   coordinates.   Denote by   ~ σ ∗   the robustly- optimal monotone solution for a given instance   〈M , S, T   〉 .  Theorem 2.   Let   G n   =   G ( X n   ∪ { S, T   } ;   r n )   be an RGG with   r n   =   ω (1)  (   log   n n  ) 1 /d  .  Then   G n   contains a monotone path   ~ σ n   ∈   Σ( S, T   )   such that   M ( ~ σ n ) = (1+ o (1)) M ( ~ σ ∗ ) , a.s.  Let   x, x ′   ∈   [0 ,   1] d   be two points such that   x      x ′ .   For a given   δ >   0   the no- tation   x    δ   x ′   indicates that   δ   = min { x ′  i   −   x i } d i =1 , where   x   = ( x 1 , . . . , x d ) , x ′   = ( x ′  1 , . . . , x ′  d ) . Given two points   x, x ′   ∈   [0 ,   1] d , such that   x      x ′ , denote by   H ( x, x ′ )  the   d -dimensional box   [ x 1 , x ′  1 ]   ×   . . .   ×   [ x d , x ′  d ] .   In addition to the assumption that the robustly-optimal solution   ~ σ ∗   is separated from the boundary of   [0 ,   1] d   that we have taken in the previous analysis, we also assume that there exists a constant   0   < δ ′′   ≤   1  such that   S    δ ′′   T   . In preparation for the main proof we prove the following lemma.  Lemma 2.   Choose any 1   f n   ∈   ω (1)   and set   r n   =   ω (1)  (   log   n n  ) 1 /d  . Let   q, q ′   ∈   [0 ,   1] d  be two points such that   q    δ   q ′ , where   δ   is independent of   n . Then a.s. there exist  1 For instance,   f n   can be either one of the following functions:   log   n,   log ∗   n , or the inverse Ackerman function   α ( n ) .
X, X ′   ∈ X n   with the following properties: (i)   ‖ X   −   q ‖ 2   ≤   r n / 2 ,   ‖ X ′   −   q ′ ‖ ≤   r n / 2 ; (ii)   q      X, X ′      q ′ ; (iii)   X, X ′   are connected in   G n   with a monotone path. Proof.   We apply a tessellation argument similar to the one used to show that the standard (and undirected) RGG is connected (see, e.g., [51, Section 2.4]).   Set   `   = ⌈   2 ‖ q ′ − q ‖ 2  r n  ⌉  and observe that   `   ≤   2 √ d/r n . Define the normalized vector   ~ v   =   q ′   − q  ‖ q ′   − q ‖ 2  and let   H 1 , . . . , H `   be a sequence of   `   hyperboxes, where  H j   =   H  (  q   + ( j   −   1)   ·   r n  2   ·   ~ v, q   +   j   ·   r n  2   ·   ~ v  )  ,  for every   1   ≤   j   ≤   `   (see Figure 1).   Observe that for every   1   ≤   j < `   and every  X j   ∈   H j   , X j +1   ∈   H j +1 , we have  X j      X j +1 ,   ‖ X j +1   −   X j   ‖ 2   ≤   r n .   (1) We show that for every   1   ≤   j   ≤   `   it follows that   X n   ∩   H j   6   =   ∅ , a.s. We start by bounding the volume of   H j   .   Denote by   c 1 , . . . , c d   the side lengths of   H j   , and denote by   δ 1 , . . . , δ d   the side lengths of   H ( q, q ′ ) . Note that   δ i   is independent of   n   and  c i   =   δ i /` . Consequently, we can represent   c i   =   α i r n , where   α i   >   0   is constant, for every   1   ≤   i   ≤   d . Thus,   | H j   |   =   cr d n   for some constant   c >   0 . Now,  Pr [ X n   ∩   H j   =   ∅ ] = (1   − | H j   | ) n   ≤   exp   {− n | H j   |}   = exp   {− ω (1)   ·   c   log   n } ≤   n − 1 .  In the last transition we used the fact that the function   f n   ∈   ω (1)   can “absorb” any constant   c . We are ready to show that every   H i   contains a point from   X n   a.s.:  Pr [ ∃ H j   :   X n   ∩   H j   =   ∅ ]   ≤  ` ∑  j =1  Pr [ X n   ∩   H i   =   ∅ ]  ≤   `   ·   n − 1   ≤   2 √ d r n  ·   n − 1   =   2 √ d ω (1)   ·   n 1 − 1 /d   log 1 /d   n .  Thus, a.s. there exists for every   1   ≤   j   ≤   `   a point   x j   ∈   H j   .   Observe that   X   :=  X 1 , X ′   :=   X `   satisfy (i),(ii). Condition (iii) follows from Equation 1.  Proof of Theorem 2.   Similarly to the proof of Theorem 1, we fix   ε >   0   and select  δ   ≤   min { δ ′ , δ ′′ }   such that   M ( ~ σ )   ≤   (1 +   ε ) M ( ~ σ ∗ )   for every   ~ σ   ∈   ~ Σ( S, T   )   with Im ( ~ σ )   ⊂ B δ   ( ~ σ ∗ )   ⊂   [0 ,   1] d . The crux of this proof is that there exists a sequence of   k   points   q 1 , . . . , q k   ∈  Im ( ~ σ ∗ ) , where   S   =   q 1 , T   =   q k , such that   q j   ≺ δ/ 2   q j +1   for every   1   ≤   j < k   (see Figure 2).   Moreover, due to fact that   ~ σ ∗   is monotone we can determine that such  k   is finite and independent of   n .   Thus, by Lemma 2, for every   1   ≤   j < k   there exist   X j   , X ′  j   ∈ X n   which satisfy the following conditions a.s.: (i)   ‖ X j   −   q j   ‖ 2   ≤  r n / 2 ,   ‖ X ′  j   −   q j +1 ‖ 2   ≤   r n / 2 ; (ii)   q j      X j   , X ′  j      q j +1 ; (iii)   X j   , X ′  j   are connected in   G n .   By conditions (i),(ii), for every   1   ≤   j < k   the graph   G n   contains the edge  ( X ′  j   , X j +1 ) . Combined with condition (iii) this implies that   S   is connected to   T   in   G n  a.s. It remains to show that the path constructed above has a cost of at most   (1 +  ε ) M ( ~ σ ∗ ) . For every   1   ≤   j   ≤   k   denote by   ~ σ j   the path induced by Lemma 2 from  X j   to   X ′  j   , i.e.,   ~ σ j   (0)   =   X j   , ~ σ j   (1) =   X ′  j   and Im ( ~ σ j   )   ⊂   H i .   Additionally, for
δ 1  δ 2  c 2  c 1  H 1  H 2  H 3  q  q ′  H ( q, q ′ )  X 1  X 2  X 3  r n / 2 Figure 1: Visualization of the proof of Lemma 2 for   d   = 2 . The blue rectangle repre- sents   H ( q, q ′ )   and the three red rectangles represent   H 1 , . . . , H `   for   `   = 3   (the small value of   `   was selected for the clarity of visualization and in reality   r n      δ 1 ). The length of the largest diagonal in each of the small rectangles is   r n / 2 , which implies that a distance between   X j   ∈   H j   , X j +1   ∈   H j +1   is at most   r n .   The blue dashed arrows represent the directed graph edges   ( X 1 , X 2 ) ,   ( X 2 , X 3 )   which correspond to a monotone path connecting   X 1   to   X 3 . every   1   ≤   j   <   k   denote by   ~ σ ′  j   the straight-line segment (sub-path) from   X ′  j   to  X j +1 . Now, define   ~ σ   to be a concatenation of   ~ σ 1 , ~ σ ′  1 , . . . , ~ σ k − 1 , ~ σ ′  k − 1 , ~ σ k . We showed in the previous paragraph that such a path exists in   G n   a.s.   Observe that for every  1   ≤   j   ≤   k   it holds that   ~ σ j   ⊂ H ( q j   , q j +1 ) , where   H ( q j   , q j +1 )   ⊂ B δ/ 2 ( ~ σ ∗ ) .   This implies that   M ( ~ σ i )   ≤   (1 +   ε ) M ( ~ σ ∗ ) . Additionally, recall that for every   1   ≤   j < k  it holds that   ‖ X ′  j   −   q j +1 ‖ 2   ≤   r n / 2 ,   ‖ X j +1   −   q j +1 ‖ 2   ≤   r n / 2 , which implies that Im ( ~ σ ′  j   )   ⊂ B r n   ( q j +1 )   ⊂ B δ   ( ~ σ ∗ ) , and consequently   M ( σ ′  j   )   ≤   (1 +   ε ) M ( ~ σ ∗ ) . Finally,  M ( ~ σ n )   ≤ M ( ~ σ )   ≤   (1 +   ε ) M ( ~ σ ∗ ) . This concludes the proof.  6   Experimental results  In this section we validate the theoretical results that were described in the previous section. We observe that the framework can cope with complex scenarios involving two or three degrees of freedom ( d   ∈ { 2 ,   3 } ), and converges quickly to the optimum. Before proceeding to the results we provide details regrading the implementa- tion.   We implemented the framework in C ++ , and tested it on scenarios involving two-dimensional objects. Nearest-neighbor search, which is used for the construction of RGGs, was implemented using   FLANN   [35]. We note that other nearest-neighbor search data structures that are tailored for the implementation of RGGs exist (see, e.g., [31]). Geometric objects, such as points, curves, and polygons were represented with   CGAL   [49].   For the representation of graphs and related algorithms we used  BOOST   [42].   Experiments were conducted on a PC with Intel i7-2600 3.4GHz pro- cessor with 8GB of memory, running a 64-bit Windows 7 OS. We proceed to describe the implementation involving the computation of non- trivial cost maps. For curve embedding we used   PQP   [20] for collision detection, i.e., determining whether a given point lies in the forbidden region   [0 ,   1] 2   \ F . Finally, the cost of an edge with respect to a given cost map was approximated by dense sampling along the edge, as is customary in motion planning (see, e.g., [33]).
δ/ 2  δ/ 2  S   =   q 1  q 2  T   =   q 3  X ′  1  X 1  X ′  2  X 2  ~ σ ∗  ~ σ 2  ~ σ 1  B δ ( ~ σ ∗ ) Figure 2: Visualization of the proof of Theorem 2 for   d   = 2   and   k   = 3 . The red curve represents   ~ σ ∗ , on which lie the points   q 1 , q 2 , q 3   such that   q 1   ≺ δ/ 2   q 2   ≺ δ/ 2   q 3 . The dashed blue curves represent   ~ σ 1 , ~ σ 2 . The gray area represents   B δ   ( ~ σ ∗ ) . The majority of running time (over %90) in the experiments below is devoted to the computation of   M   for given point samples or edges. Thus, we report only the overall running time in the following experiments. We mention that we also implemented a simple grid-based method for the purpose of comparison with the framework. How- ever, it performed poorly in easy scenarios and did not terminate in hard cases. Thus, we chose to omit theses results here. Unless stated otherwise, we use in the experiments the connection radius which is described in Theorem 1, and denote it by   r ∗  n . This applies both to the standard and strong regimes of the problem.   A discussion regarding the connection radius in the strong regime appears below in Section 6.3.  6.1   Various scenarios  In this set of experiments we demonstrate the flexibility of the framework and test it on the three different scenarios. We emphasize that we employ a shared code framework to solve these three problems and the ones described later. The only difference in the implementation lies in the type of cost function used.   The following problems are solved using a planner for the   strong   case of BPP. Figure 3 (left) depicts an instance of   P1   (see Section 3.1), which consists of two geometrically-identical curves (red and blue). The curves are bounded in   [0 ,   1] 2   and the red curve is translated by   (0 . 05 ,   0 . 05)   from the blue curve. The optimal solution has a cost of   0 . 07 , in which the curves are traversed identically. Our program was able to produce a solution of cost   0 . 126   in   27   seconds and   n   = 100 , 000   samples. Results reported throughout this section are the averaged over   10   trials. Figure 4 (left) depicts an instance of   P2 . The goal is to find a traversal of the three curves such that the traversal point along the purple curve is visible from either the blue or red curve, while of course minimizing the lengths of the leashes between the three curves. Note that the view can be obstructed by the gray rectangular obstacles. A trivial, albeit poor, solution is to move the point along the purple curve from start to end, while the traversal point of, say, the red curve stays put in the start position. A much
Figure 3: Scenarios involving two curve.  Figure 4: Scenarios involving curves and obstacles. better solution, which maintains short leashes, is described as follows: we move along the purple curve until reaching the first resting point, indicated by the leftmost black disc. Then we move along the red curve until we reach to the position directly below the black circle. Only then we move along the blue curve from start until reaching the point directly below the first black disc. We use a similar parametrization with respect to the second “pit stop”, and so on. Such a solution was obtained by our program in   11  seconds using   n   = 20 , 000   samples. Figure 4 (right) depicts an instance of   P3 . The input consists of a curve (depicted in red), and polygonal obstacles (depicted in gray). The solution obtained by our program after   600   seconds with   n   = 100 , 000 , is drawn in blue.  6.2   Increasing difficulty  Here we focus on   P1   for two curves in the standard regime. We study how the difficulty of the problem affects the running time and the rate of convergence of the returned cost. We start with a base scenario, depicted in Figure 3 (right), and gradually increase its difficulty.   In the depicted scenario the bottom (blue) curve consists of five circular loops of radius   0 . 15 , where the entrance and exit point to each circle is indicated by a bullet.   The top curve is similarly defined, and the two curves are separated by a vertical distance of   0 . 04 . The optimal matching of cost   0 . 34   is obtained in the following manner: when a given circle of the red curve is traversed, the position along the blue
0.34 0.36 0.38 0.4 0.42 0.44 0.46 0.48 0.5  Cost 0   20000   40000   60000   80000   100000   120000  Samples  80 loops 40 loops 20 loops 10 loops 5 loops Figure 5: Results for scenarios of increasing difficulty, as described in Section 6.2. curve is fixed to the entrance point of the circle directly below the traversed circle, and vice versa. In a similar fashion we construct scenarios with 10,20,40 and 80 loops in each curve. In Figure 5 we report for each of the scenarios the cost of the obtained solution as a function of the number of samples   n .   We set   n   = 2 i   for the integer value   i  between   12   and   18 . For   i   = 12   and   i   = 18   the running times were roughly   2   and   66  seconds, respectively. In between, the values were linearly proportional to the number of samples (results omitted). Observe that as the difficulty of the problem increases the convergence rate of the cost slightly decreases, but overall a value near the optimum is reached fairly quickly.  6.3   Connection radius in the strong regime  Here we consider the   strong   regime and study the behavior of the framework for varying connection radii.   For this purpose, we use the two-curves scenario with 20 loops that was described in Section 6.2. We set the connection radius to   r n   :=   g n   ·  r ∗  n , where   r ∗  n   is the radius of the standard regime (see Theorem 1).   We set   g n   ∈ { 1 ,   1 . 1 ,   log log   n   + 1 ,   √ log   n } . Results are depicted in Figure 6. Not surprisingly, larger values of   r n   lead to quicker convergence, in terms of the number of samples required, to the optimum. However, this comes at the price of a denser RGG, which results in poor running times. Note that the program terminated due to lack of space for the two largest functions of   g n   for   n   = 128 , 000 . Interestingly, the connection radius   r ∗  n   of the standard regime seems to converge to the optimum, albeit slowly. This leads to the question whether such a function also results in connec- tivity in the strong regime. Note that our proof of the convergence in the strong regime requires a larger value of   r n   (see Theorem 2).  6.4   Increasing dimensionality  We test how the dimension of the configuration space   d   affects the performance. For this purpose we study the behavior of the framework on   weak   k -curve Fr ́ echet distance with   k   ranging from   2   to   5 . For   k   = 2   we use the scenario described in Section 6.2 with   10   loops. For   k   = 3   we add another copy of the blue curve, for   k   = 4   an additional copy of the red curve, and another blue curve for   k   = 5 . We report running time and cost in Figure 7 for various values of   n , as described earlier. Note that that for   k   = 4   the program ran out of memory for   n   = 64 , 000 , and for   k   = 5   around   n   = 32 , 000 . This phenomena occurs since the connection radius
0.35 0.4 0.45 0.5 0.55  Cost 0   20000   40000   60000   80000   100000   120000  Samples  √ log   n   ·   r ∗  n  (1 + log log   n )   ·   r ∗  n  1 . 1   ·   r ∗  n  r ∗  n 0 50 100 150 200 250 300  Time [sec] 0   20000   40000   60000   80000   100000   120000  Samples  √ log   n   ·   r ∗  n  (1 + log log   n )   ·   r ∗  n  1 . 1   ·   r ∗  n  r ∗  n Figure 6: Results for varying connection radii in the strong regime, as described in Section 6.3. 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65  Cost 0   20000   40000   60000   80000   100000   120000  Samples  5 curves 4 curves 3 curves 2 curves 0 200 400 600 800 1000 1200  Time [sec] 0   20000   40000   60000   80000   100000   120000  Samples  5 curves 4 curves 3 curves 2 curves  Figure 7: Figures for the first set of experiments, as described in Section 6.4 obtained in Theorem 1 grows exponentially in   d . In particular, for   r n   =   γ  (   log   n n  ) 1 /d  , where   γ   = 2(2 dθ d ) − 1 /d , each sample has in expectancy   Θ(2 d   log   n )   neighbors in the obtained RGG.  References  [1] A. Adler, M. de Berg, D. Halperin, and K. Solovey. Efficient multi-robot motion planning for unlabeled discs in simple polygons.   IEEE Trans. Automation Science and Engineering , 12(4):1309–1317, 2015. [2] H. Alt and M. Godau. Computing the Fr ́ echet distance between two polygonal curves.   Int. J. Comput. Geometry Appl. , 5:75–91, 1995. [3] O. Arslan and P. Tsiotras.   Use of relaxation methods in sampling-based algo- rithms for optimal motion planning. In   Robotics and Automation (ICRA), 2013 IEEE International Conference on , pages 2421–2428. IEEE, 2013. [4] F. Avnaim, J.-D. Boissonnat, and B. Faverjon. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles.   In   Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on , pages 1656–1661. IEEE, 1988. [5] P. Balister, A. Sarkar, and B. Bollob ́ as. Percolation, connectivity, coverage and colouring of random geometric graphs. In B. Bollob ́ as, R. Kozma, and D. Mikl ́ os, editors,   Handbook of Large-Scale Random Networks , pages 117–142. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.
[6] K. Bringmann. Why walking the dog takes time: Fr ́ echet distance has no strongly subquadratic algorithms unless SETH fails. In   Foundations of Computer Science , pages 661–670, 2014. [7] K. Bringmann and W. Mulzer. Approximability of the discrete Fr ́ echet distance.  Journal of Computational Geometry , 7(2):46–76, 2016. [8] N. Broutin, L. Devroye, N. Fraiman, and G. Lugosi. Connectivity threshold of bluetooth graphs.   Random Struct. Algorithms , 44(1):45–66, 2014. [9] K. Buchin, M. Buchin, M. Konzack, W. Mulzer, and A. Schulz.   Fine-grained analysis of problems on curves. In   EuroCG, Lugano, Switzerland , 2016. [10] K. Buchin, M. Buchin, W. Meulemans, and W. Mulzer. Four soviets walk the dog - with an application to Alt’s conjecture. In   ACM-SIAM Symposium on Discrete Algorithms , pages 1399–1413, 2014. [11] K. Buchin, M. Buchin, and A. Schulz. Fr ́ echet distance of surfaces: Some simple hard cases. In   European Symposium of Algorithms , pages 63–74, 2010. [12] K. Buchin, M. Buchin, R. van Leusden, W. Meulemans, and W. Mulzer. Com- puting the Fr ́ echet distance with a retractable leash. In   European Symposium of Algorithms , pages 241–252, 2013. [13] K. Buchin, M. Buchin, and C. Wenk. Computing the Fr ́ echet distance between simple polygons.   Comput. Geom. , 41(1-2):2–20, 2008. [14] E. W. Chambers,    ́ E. C. de Verdi` ere, J. Erickson, S. Lazard, F. Lazarus, and S. Thite.   Homotopic Fr ́ echet distance between curves or, walking your dog in the woods in polynomial time.   Comput. Geom. , 43(3):295–311, 2010. [15] S. Chechik, H. Kaplan, M. Thorup, O. Zamir, and U. Zwick. Bottleneck paths and trees and deterministic graphical games. In   Symposium on Theoretical Aspects of Computer Science , pages 27:1–27:13, 2016. [16] A. F. Cook and C. Wenk.   Geodesic Fr ́ echet distance inside a simple polygon.  ACM Transactions on Algorithms , 7(1):9, 2010. [17] M. de Berg and M. J. van Kreveld. Trekking in the alps without freezing or getting tired.   Algorithmica , 18(3):306–323, 1997. [18] A. Dumitrescu and G. Rote. On the Fr ́ echet distance of a set of curves. In   Cana- dian Conference on Computational Geometry , pages 162–165, 2004. [19] C. Fan, O. Filtser, M. J. Katz, T. Wylie, and B. Zhu. On the chain pair simplifica- tion problem. In   Symposium on Algorithms and Data Structures , pages 351–362, 2015. [20] GAMMA group. PQP - a proximity query package, 1999. University of North Carolina at Chapel Hill, USA. [21] D. Halperin and M. Sharir. A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment.   Discrete & Computational Geometry , 16(2):121–134, 1996.
[22] S. Har-Peled and B. Raichel. The Fr ́ echet distance revisited and extended.   ACM Transactions on Algorithms , 10(1):3, 2014. [23] J. E. Hopcroft, J. T. Schwartz, and M. Sharir.   On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the “Warehouse- man’s problem”.   International Journal of Robotics Research , 3(4):76–88, 1984. [24] D. Hsu, J. Latombe, and R. Motwani. Path planning in expansive configuration spaces.   Int. J. Comput. Geometry Appl. , 9(4/5):495–512, 1999. [25] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponen- tial complexity?   J. Comput. Syst. Sci. , 63(4):512–530, 2001. [26] L. Janson, E. Schmerling, A. A. Clark, and M. Pavone. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimen- sions.   I. J. Robotic Res. , 34(7):883–921, 2015. [27] M. Jiang, Y. Xu, and B. Zhu. Protein structure–structure alignment with discrete Fr ́ echet distance.   Journal of bioinformatics and computational biology , 6(01):51– 64, 2008. [28] S. Karaman and E. Frazzoli. Sampling-based algorithms for optimal motion plan- ning.   International Journal of Robotics Research , 30(7):846–894, 2011. [29] L. E. Kavraki, P. ˇ Svestka, J.-C. Latombe, and M. H. Overmars.   Probabilistic roadmaps for path planning in high dimensional configuration spaces.   IEEE Transactions on Robotics and Automation , 12(4):566–580, 1996. [30] L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap. Classroom examples of robustness problems in geometric computations.   Comput. Geom. , 40(1):61–78, 2008. [31] M. Kleinbort, O. Salzman, and D. Halperin. Efficient high-quality motion plan- ning by fast all-pairs r-nearest-neighbors. In   IEEE International Conference on Robotics and Automation , pages 2985–2990, 2015. [32] J. J. Kuffner and S. M. LaValle. RRT-Connect: An efficient approach to single- query path planning.   In   International Conference on Robotics and Automation (ICRA) , pages 995–1001, 2000. [33] S. M. LaValle.   Planning algorithms . Cambridge University Press, 2006. [34] W. Meulemans. Map matching with simplicity constraints.   CoRR , abs/1306.2827, 2013. [35] M. Muja and D. G. Lowe.   Fast approximate nearest neighbors with automatic algorithm configuration. In   VISSAPP , pages 331–340. INSTICC Press, 2009. [36] M. Penrose.   Random geometric graphs , volume 5.   Oxford University Press, 2003. [37] B. Raveh, A. Enosh, O. Schueler-Furman, and D. Halperin.   Rapid sampling of molecular motions with prior information constraints.   PLoS Computational Biology , 5(2), 2009.
[38] J. H. Reif.   Complexity of the movers problem and generalizations: Extended abstract. In   Foundations of Computer Science , pages 421–427, 1979. [39] O. Salzman and D. Halperin.   Asymptotically-optimal motion planning using lower bounds on cost.   In   IEEE International Conference on Robotics and Au- tomation (ICRA) , pages 4167–4172, 2015. [40] M. Sharir.   Algorithmic motion planning.   In J. E. Goodman and J. O’Rourke, editors,   Handbook of Discrete and Computational Geometry, Second Edition. , pages 1037–1064. Chapman and Hall/CRC, 2004. [41] J. Sherette and C. Wenk. Simple curve embedding.   CoRR , abs/1303.0821, 2013. [42] J. G. Siek, L.-Q. Lee, and A. Lumsdaine.   The Boost Graph Library User Guide and Reference Manual . Addison-Wesley, 2002. [43] K. Solovey and D. Halperin.   On the hardness of unlabeled multi-robot motion planning. In   Robotics: Science and Systems (RSS) , 2015. [44] K. Solovey, O. Salzman, and D. Halperin.   Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot mo- tion planning.   International Journal of Robotics Research , 35(5):501–513, 2016. [45] K. Solovey, O. Salzman, and D. Halperin. New perspective on sampling-based motion planning via random geometric graphs. In   Robotics: Science and Systems (RSS) , Ann Arbor, Michigan, 2016. [46] K. Solovey, J. Yu, O. Zamir, and D. Halperin.   Motion planning for unlabeled discs with optimality guarantees. In   Robotics: Science and Systems (RSS) , 2015. [47] P. G. Spirakis and C.-K. Yap. Strong NP-hardness of moving many discs.   Infor- mation Processing Letters , 19(1):55–59, 1984. [48] R. Sriraghavendra, K. Karthik, and C. Bhattacharyya.   Fr ́ echet distance based approach for searching online handwritten documents.   In   Document Analysis and Recognition , volume 1, pages 461–465. IEEE, 2007. [49] The CGAL Project.   CGAL user and reference manual . CGAL editorial board, 4.8 edition, 2016. [50] M. Turpin, N. Michael, and V. Kumar. Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In   International Conference on Robotics and Automation (ICRA) , pages 842–848, 2013. [51] M. Walters. Random geometric graphs. In R. Chapman, editor,   Surveys in Com- binatorics 2011 , chapter 8, pages 365–401. Cambridge University Press, 2011. [52] V. V. Williams.   Efficient Algorithms for Path Problems in Weighted Graphs . Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, 2008. [53] J. Zheng, X. Gao, E. Zhan, and Z. Huang.   Algorithm of on-line handwriting signature verification based on discrete Fr ́ echet distance. In   Advances in Compu- tation and Intelligence , pages 461–469. Springer, 2008.