Computing the Fréchet distance between piecewise smooth curves

Computing the Frehet Distane b etween Pieewise Smo oth Curves ? G unter Rote Freie Universitat Berlin, Institut fur Informatik, Takustrae 9, 14195 Berlin, Germany, roteinf.fu-berlin.de. Abstrat We onsider the Frehet distane between two urves whih are given as a sequene of m + n urved piees. If these piees are suÆiently well-b ehaved, we an ompute the Frehet distane in O ( mn log ( mn )) time. The deision version of the problem an b e solved in O ( mn ) time. 1. Intro dution The Frehet distane is a distane measure b etween urves. Denition 1 (Frehet distane) Let f : I = [ l I ; r I ℄ ! R 2 and g : J = [ l J ; r J ℄ ! R 2 be two planar urves, and let kk denote the Eu- lidean norm. Then the Frehet distane Æ F ( f ; g ) is dened as Æ F ( f ; g ) := inf  : [0 ; 1℄ ! I  : [0 ; 1℄ ! J max t 2 [0 ; 1℄ k f (  ( t ))  g (  ( t )) k : where  and  range over ontinuous and nondereasing reparameterizations with  (0) = l I ,  (1) = r I ,  (0) = l J ,  (1) = r J . In ontrast to other ommon distane measures like the Hausdor distane, the Frehet distane resp ets the one-dimensional struture of the urves and do esn't just treat them as a point set. The study of the Frehet distane from a omputational p oint of view has b een initiated by Alt and Go dau [2℄. The deision problem is the problem to deide, for a given " , whether the Frehet distane b etween two urves is at most " . Alt and Godau [2℄ treated the ase of two polygonal urves. For two urves of m and n piees, resp etively, they showed how to solve the deision problem in O ( mn ) time and the optimization prob- ? Partially supported by the IST Programme of the EU as a Shared-ost RTD (FET Op en) Pro jet under Contrat No IST-2000-26473 (ECG|Eetive Computational Geometry for Curves and Surfaes). lem in O ( mn log( mn )) time. Some related problems have also been onsidered, like minimizing the Frehet distane under translations [3℄, or a generalized Frehet distane b etween a urve and a graph [1℄. In all ases, however, the ob jets are pieewise linear. In this pap er, we explore the Frehet distane b etween more general urves. We assume that eah input urve is given as a sequene of smo oth urve piees that are\suÆiently well-b ehaved", suh as irular ars, parab oli ars, or some lass of spline urves. Our algorithm will p erform ertain op erations on these urves, like interseting them with a irle. We will show that the ombinatorial omplexity , i. e., the number of steps, for solving the deision problem is not larger than for p olygonal paths, O ( mn ). The omplexity of the individual op erations (the algebrai omplexity ) dep ends of ourse on the nature of the urves. Under the stronger assumption that the urves onsist of algebrai piees whose degree is bounded by a onstant, we an solve the optimization problem in O ( mn log( mn )), thus mathing the running time for the polygonal ase. The elementary op erations, however, are algebrai op erations of higher degree. We assume that eah urve is given as a sequene of piees whih are onneted at their endp oints. Every piee is a smo oth urve of lass C 2 , i. e., the urvature is dened everywhere and varies ontinuously within a piee. We will not make any assumptions how the urves are given; it is only imp ortant that the neessary geometri op erations 20th EWCG Seville, Spain (2004) 20th Europ ean Workshop on Computational Geometry an b e arried out. We need urves whose turning angle is bounded by  . Curves of larger b ounding angle must b e sub divided. For solving the deision problem with parameter " , we sub divide the urve at all points where the urvature is 1 =" , in order to ensure that in eah piee of the urve, the urvature is either uniformly smaller or bigger than 1 =" . We have omitted most pro ofs, but we state one auxiliary lemma in order to illustrate the elementary arguments on whih the results are based. Lemma 2 Let f be a smooth urve of turning angle at most  , and let  by a irle of radius r . (a) If the urvature of f is at most 1 =r everywhere, the urve an interset  at most twie. If it intersets  twie, then its endpoints lie outside  or on the boundary, and the midd le piee between the two intersetions lies inside  . (b) If the urvature of f is at least 1 =r everywhere, the urve an interset  at most twie. The full version of this pap er is available as a tehnial rep ort [5℄. 2. The Free Spae Diagram The main to ol of the algorithm is the free spae diagram whih was intro dued in [2℄. It is a twodimensional representation of all pairs of p oints on the two urves, together with the identiation of those pairs whih are loser than " . Denition 3 Let f : I ! R 2 , g : J ! R 2 be two urves, I ; J  R . The set F " ( f ; g ) := f ( s; t ) 2 I  J : k f ( s )  g ( t ) k  " g denotes the free spae of f and g . the partition of I  J into the free spae and its omplement is al led the free spae diagram . Points in F " are alled feasible or free , and they are usually drawn in white. The other p oints are alled forbidden points or obstales , see Figure 1. The following simple observation from [2℄ is ruial. Lemma 4 Let f : I = [ l I ; r I ℄ ! R 2 , g : J = [ l J ; r J ℄ ! R 2 be two urves. Then Æ F ( f ; g )  " if and only if there exists a urve within F " ( f ; g ) from ( l I ; l J ) to ( r I ; r J ) whih is monotone in both oordinates. 2 As f and g onsist of several piees, the free spae diagram deomp oses naturally into a grid of retangular el ls . ε f g Fig. 1. Two p olygonal urves and their free spae diagram. The sale of the free spae diagram is 50% redued with resp et to the urves. 3. Critial p oints We regards as ritial points on the b oundary of F " those p oints whih are lo al extrema in the horizontal or vertial diretion. There are eight lasses of ritial p oints, shown in Figure 2. W+ N+ S+ E+ N− E− S− W− Fig. 2. The eight types of ritial p oints. N , S , E , W refers to the diretion in whih the p oint is extreme, and the sup ersript tells whether the area in this diretion is feasible (+) or forbidden (  ). In terms of the urves f and g , these p oints orresp ond to situations where a irle  of radius " around a point of one urve is tangent to the other urve. For example, a ritial point of typ e W + o - urs in the situation where g touhes the irle  of radius " around a p oint x on f from inside. As x pro eeds further away from g , a portion of g b egins to stik out from  . Marh 25-26, 2004 Seville (Spain) 4. The struture of a single ell The free spae may b e arbitrarily ompliated even inside a ell. For example, if " is very small, F " will ontain isolated islands of free spae for all intersetions b etween f and g . However, we will show that the reahable p oints an b e omputed in a onstant numb er of elementary geometri operations. We have sub divided the urves, and onsequently, the parameter intervals I and J into m and n piees, resp etively. Corresp ondingly, we ut the retangle I  J into mn ells. On the b oundaries of these ells, we ompute all p oints whih are reahable from the lower left orner ( l I ; l J ) of the retangle by a path in free spae whih is monotone in b oth diretions. We do this inrementally from the lower left ell to the upp ermost right ell. A vertial line in the free-spae diagram orresp onds to a xed p oint f ( s ) on f . The p oints in F " on this line orrespond to the points of g whih lie inside a irle  of radius " around f ( s ). The b oundary of F " orresp onds to the intersetions of  with g , and hene we an apply Lemma 2. Lemma 5 Inside a el l, a vertial or horizontal line intersets the boundary of F " at most twie. A vertial tangent line trough a ritial point of type E or W or a horizontal tangent line trough a ritial point of type N or S does not ross the boundary of F " in any other point. 2 Lemma 6 A urve forming a omponent of the boundary of the free spae inside a el l an ontain at most four ritial points. 2 This lemma implies that there is a limited numb er of p ossibilities for suh a b oundary, the most ompliated b eing an \s-shaped" path between b etween the left edge and the right edge of the retangle, ontaining two ritial p oints S + and N  . 5. Pro essing a ell We are given the reahable p oints on the left and b ottom edge, and we ompute the p oints on the right edge and on the top edge whih are reahable from there. On eah edge of the retangle there are at most two intervals of free p oints, by Lemma 5. Inside eah interval of free points, there is only a single interval of reahable p oints b eause from every free p oint, everything whih is to the right or to the top in the same free interval is reahable diretly. We will illustrate how to ompute the leftmost reahable p oint in eah free interval on the top edge from a given interval X on left edge. Other ases are similar. We are given the lowest reahable p oint B in X . The upper end of X may b e the upp er left orner of the retangle, or it may b e a forbidden p oint whih belongs to a omp onent O of forbidden p oints. Similarly, the left endp oint F of Y may b e part of a omponent of forbidden points, whih we denote by O 2 . ( O and O 2 are not neessarily dierent, see Figure 3a.) Lemma 7 The leftmost point U in Y reahable from X depends only on the presene and the relative loations of O and O 2 and the horizontal line through B . PROOF. We have to show that any other \obstales" of forbidden p oints do not play any role in this question. We show this by giving an algorithm for onstruting U in all ases. If the horizontal line through B intersets O or O 2 , it is lear that one annot reah Y , see for example the interval X 1 in Figure 3a or the interval X 2 in onnetion with Y 2 in Figure 3b. Otherwise, we laim that the desired p oint U lies diretly ab ove the rightmost p oint of O or of O 2 , whihever is further to the right. The monotone path from X to Y has to pass to the right of O and O 2 . Thus, no point in Y left of U is reahable from X . To see that U is reahable, onsider rst the ase that O exists, see the example of the interval X 1 in Figure 3b. Let A b e the rightmost p oint of O . A an lie on the upper edge, or it an b e a ritial p oint of typ e E + . Assume rst that A is a ritial p oint of typ e E + . The vertial line a through A lies ompletely in the free spae, by Lemma 5, and O is the only obstale left of a . By assumption, the horizontal line b from the lowest reahable p oint B in X do es not interset O b efore reahing a , and there are no other obstales in this range. Thus, A is reahable from B , and the upp er end A 0 of a is the leftmost reahable p oint on the top edge. If it lies in Y , we an take it as our p oint U , and we are done. (This is the ase for the intervals X 1 and Y 1 in Figure 3b.) If Y lies left of a , we are done as well, as no p oints in Y are reahable from X . So let us deal with the 20th Europ ean Workshop on Computational Geometry B O F AB B2 a A′ A O b O2 FC′ C (a) (b) D Y1Y2Y1Y2 X2 X1 X2 X1 Fig. 3. Determining the reahable p oints on the top edge only remaining ase that Y lies to the right of a , and a is separated from Y by the obstale O 2 . The lowest p oint D of O 2 must lie ab ove O , and the horizontal line through D intersets a , whih is reahable. Therefore D is reahable. From D we an reah the rightmost p oint C of O 2 , whih is either a ritial point of typ e E + or the p oint F . In either ase, we an indeed reah the point C 0 vertially ab ove C as the leftmost p oint U . The ases when O do es not exist, or when the rightmost point A of O lies on the upp er edge, an b e treated similarly. 2 Will have desrib ed our proedure in terms of geometri op erations in the free spae diagram, like nding the right-most point in a omp onent of forbidden p oints. By working out what these operations mean in terms of the urves f and g , we obtain the following theorems. Theorem 8 Given the reahable points on the bottom edge and the left edge of a el l, the reahable points on the top edge and the right edge of the el l an be omputed in a onstant number of the following operations: { Interseting a irle of radius " with one of the urves { Finding the rst intersetion of one urve with an oset urve of the other urve at distane " . In both ases, we must be able to nd the parameter values on the respetive urves, orresponding to the points that we have omputed. 2 Theorem 9 Given two urves onsisting of m and n piees, respetively, where eah piee has a turning angle at most  and has urvature  " or  " throughout, we an deide O ( m + n ) spae and in O ( mn ) primitive operations of the type desribed in Theorem 8 whether their Frehet distane is at most " , for a given parameter " . 2 6. The Minimization Problem The minimization problem of omputing the Frehet distane an b e solved by Megiddo's parametri searh tehnique [4℄, losely following the approah of [2℄ for p olygonal urves. The tehnial details are more involved, and we have to make some stronger assumptions on the urves. Theorem 10 Given two urves onsisting of m and n piees, respetively, of smooth algebrai urves of xed maximum degree we an ompute their Frehet distane in O ( nm ) spae and in O ( mn log( mn )) algebrai operations, i.e., degree omparison between two real solutions of algebrai equations of bounded degree. 2 Referenes [1℄ H. Alt, A. Efrat, G. Rote, and C. Wenk, Mathing planar maps , Journal of Algorithms 49 (2003), 262{283. [2℄ H. Alt and M. Go dau, Computing the Frehet distane between two polygonal urves , Internat. J. Comput. Geom. Appl. 5 (1995), 75{91. [3℄ H. Alt, C. Knauer, and C. Wenk, Mathing polygonal urves with respet to the Frehet distane , STACS 2001 (A. Ferreira and H. Reihel, eds.), Let. Notes Comp. Si., vol. 2010, Springer-Verlag, 2001, pp. 63{74. [4℄ N. Megiddo, Applying paral lel omputation algorithms in the design of serial algorithms , J. Asso . Comput. Mah. 30 (1983), 852{865. [5℄ G unter Rote, Computing the frehet distane between pieewise smooth urves , Teh. Rep ort ECG-TR- 241108-01, 2003.