{"id":1715,"date":"2021-01-24T13:45:23","date_gmt":"2021-01-24T13:45:23","guid":{"rendered":"http:\/\/192.168.31.181\/muthu\/?p=1715"},"modified":"2021-05-24T03:53:08","modified_gmt":"2021-05-24T03:53:08","slug":"computing-the-discrete-frechet-distance-using-dynamic-programming","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/computing-the-discrete-frechet-distance-using-dynamic-programming\/","title":{"rendered":"Computing the discrete Fr\u00e9chet distance using dynamic programming"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Definition<\/h2>\n\n\n\n<p>The Fr\u00e9chet distance is usually explained using the analogy of a man walking his dog.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"483\" height=\"83\" src=\"http:\/\/35.93.160.39\/wp-content\/uploads\/2021\/01\/man-dog.png\" alt=\"\" class=\"wp-image-1717\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/man-dog.png 483w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/man-dog-300x52.png 300w\" sizes=\"(max-width: 483px) 100vw, 483px\" \/><\/figure>\n\n\n\n<p>A man is walking a dog on a leash: the man can move on one curve, the dog on the other; both may vary their speed, but backtracking is not allowed. What is the length of the shortest leash that is sufficient for traversing both curves?<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition<\/h2>\n\n\n\n<p>We can formally define it as: <\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"110\" src=\"http:\/\/35.93.160.39\/wp-content\/uploads\/2021\/01\/image-1024x110.png\" alt=\"\" class=\"wp-image-1726\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-1024x110.png 1024w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-300x32.png 300w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-768x83.png 768w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-780x84.png 780w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image.png 1448w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Given two sequence of points in \\(\\mathbb{R}^d \\), p={p1, p2, p3&#8230;..pn} and q= {q1, q2, q3&#8230;. qm}, Fr\u00e9chet distance represented by \\(f(x,y) \\) is the maximum of the minimum distances between points p<sub>i<\/sub> and q<sub>i<\/sub>.  To understand it more intuitively, let us look at a simple example. <\/p>\n\n\n\n<p>In the below graph, I have two set of polylines with positions:<\/p>\n\n\n\n<p>\\(P = {(2,1) , (3,1), (4,2), (5,1)} \\)<br>\\(Q = {(2,0),(3,0),(4,0)} \\)<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"451\" src=\"http:\/\/35.93.160.39\/wp-content\/uploads\/2021\/01\/image-2-1024x451.png\" alt=\"\" class=\"wp-image-1734\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-2-1024x451.png 1024w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-2-300x132.png 300w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-2-768x338.png 768w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-2-780x343.png 780w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/image-2.png 1450w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Starting and ending points being (p1,q1) and (p4,q3) respectively.<\/p>\n\n\n\n<p>We find all the pairs of walks between p and q given as,<\/p>\n\n\n\n<p>\\(p1 -&gt; (p1, q1) , (p1,q2), (p1,q3)\\)<br>\\(p2 -&gt; (p2, q1), (p2,q2), (p2,q3) \\)<br>\\(p3 -&gt; (p3, q2), (p3,q2), (p3,q3) \\)<br>\\(p4 -&gt; (p4, q2), (p4,q2), (p4,q3) \\)<\/p>\n\n\n\n<p>then, we find the minimum distances for each pair.<\/p>\n\n\n\n<p>\\(min\\{p1\\} = min\\{dist(p1,q1), dist(p1,q2), dist(p1,q3)\\} = min\\{1, 1.4, 2.2\\} = 1 \\)<br>\\(min\\{p2\\} = min\\{dist(p2,q1), dist(p2,q2), dist(p2,q3)\\} = min\\{1.4, 1, 1.4\\} = 1\\)<br>\\(min\\{p3\\} = min\\{dist(p3,q1), dist(p3,q2), dist(p3,q3)\\} = min\\{2.8, 2.2, 2\\} = 2 \\}\\)<br>\\(min\\{p4\\} = min\\{dist(p3,q1), dist(p3,q2), dist(p3,q3)\\} = min\\{3.2, 2.2, 2\\} = 2\\)<\/p>\n\n\n\n<p>Now, we can find the Fr\u00e9chet distance by finding the maximum of all the minimums we calculated in the last step.<\/p>\n\n\n\n<p>\\(f(x,y) = max\\{min\\{p1\\}, min\\{p2\\}, min\\{p3\\}, min\\{p4\\}\\} = max\\{1,1,2,2\\} = 2 \\)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Implementation<\/h2>\n\n\n\n<p>The implementation described by Thomas Eiter and Heikki Mannila <sub><sup>[1]<\/sup><\/sub> uses dynamic programming to reduce the time complexity of finding the Fr\u00e9chet distance by navigating through only three possible paths.<\/p>\n\n\n\n<ul class=\"has-black-color has-very-light-gray-to-cyan-bluish-gray-gradient-background has-text-color has-background\"><li>P and Q both move one step<\/li><li>P stays where it is, Q moves one step<\/li><li>P moves one step, Q stays where it is<\/li><\/ul>\n\n\n\n<p>This reduces the total number of pairs for each point in P. The implementation is as below:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>from scipy.spatial.distance import euclidean\nimport seaborn as sns\n\nP = &#091;&#091;2,1] , &#091;3,1], &#091;4,2], &#091;5,1]]\nQ = &#091;&#091;2,0] , &#091;3,0], &#091;4,0]]\n\np_length = len(P)\nq_length = len(Q)\ndistance_matrix = np.ones((p_length, q_length)) * -1\n\n# fill the first value with the distance between \n# the first two points in P and Q\ndistance_matrix&#091;0, 0] = euclidean(P&#091;0], Q&#091;0])\n\n# load the first column and first row with distances (memorize)\nfor i in range(1, p_length):\n    distance_matrix&#091;i, 0] = max(distance_matrix&#091;i-1, 0], euclidean(P&#091;i], Q&#091;0]))\nfor j in range(1, q_length):\n    distance_matrix&#091;0, j] = max(distance_matrix&#091;0, j-1], euclidean(P&#091;0], Q&#091;j]))\n\nfor i in range(1, p_length):\n        for j in range(1, q_length):\n            distance_matrix&#091;i, j] = max(min(distance_matrix&#091;i-1, j], distance_matrix&#091;i, j-1], distance_matrix&#091;i-1, j-1]),\n                           euclidean(P&#091;i], Q&#091;j]))\ndistance_matrix&#091;p_length-1, q_length-1]       \nsns.heatmap(distance_matrix, annot=True)<\/code><\/pre>\n\n\n\n<p>The preview of our sample as a heatmap is as below: <\/p>\n\n\n\n<div class=\"wp-block-image is-style-default\"><figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/35.93.160.39\/wp-content\/uploads\/2021\/01\/heatmap.png\" alt=\"\" class=\"wp-image-1736\" width=\"425\" height=\"296\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/heatmap.png 356w, http:\/\/write.muthu.co\/wp-content\/uploads\/2021\/01\/heatmap-300x209.png 300w\" sizes=\"(max-width: 425px) 100vw, 425px\" \/><figcaption>distance matrix heatmap<\/figcaption><\/figure><\/div>\n\n\n\n<h4 class=\"wp-block-heading\">References:<\/h4>\n\n\n\n<p class=\"has-small-font-size\">[1] Thomas Eiter and Heikki Mannila. Computing discrete Frechet<br>distance. Technical report, 1994. <a rel=\"noreferrer noopener\" href=\"http:\/\/www.kr.tuwien.ac.at\/staff\/eiter\/et-archive\/cdtr9464.pdf\" target=\"_blank\">http:\/\/www.kr.tuwien.ac.at\/staff\/eiter\/et-archive\/cdtr9464.pdf<\/a><\/p>\n\n\n\n<p class=\"has-small-font-size\">[2] Jupyter Notebook with Frechet distance implementation.<br><a href=\"https:\/\/colab.research.google.com\/drive\/1Cht2BSmKs6vCNfQZisoxMFZ_9eYMDrIi\">https:\/\/colab.research.google.com\/drive\/1Cht2BSmKs6vCNfQZisoxMFZ_9eYMDrIi<\/a><a rel=\"noreferrer noopener\" href=\"http:\/\/www.kr.tuwien.ac.at\/staff\/eiter\/et-archive\/cdtr9464.pdf\" target=\"_blank\"><br><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Definition The Fr\u00e9chet distance is usually explained using the analogy of a man walking his dog. A man is walking a dog on a leash: the man can move on one curve, the dog on the other; both may vary their speed, but backtracking is not allowed. What is the length of the shortest leash [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1736,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,24,6],"tags":[],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1715"}],"collection":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/comments?post=1715"}],"version-history":[{"count":21,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1715\/revisions"}],"predecessor-version":[{"id":1909,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1715\/revisions\/1909"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1736"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1715"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1715"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1715"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}