{"id":13325,"date":"2021-12-09T20:37:34","date_gmt":"2021-12-10T01:37:34","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13325"},"modified":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","slug":"tr-10-08-frechet-distance-with-speed-limits","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2010\/tr-10-08-frechet-distance-with-speed-limits\/","title":{"rendered":"TR-10-08: Frechet Distance with Speed Limits"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-10-08: Frechet Distance with Speed Limits\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-10-08
\nApril 27, 2010<\/p>\n\n\n\n

Frechet Distance with Speed Limits<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n

Anil Maheshwari, Jorg-Rudiger Sack, Kaveh Shahbaz, Hamid Zarrabi-Zadeh<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

In this paper, we introduce a new generalization of the well-known Frechet distance between two polygonal curves, and provide an efficient algorithm for computing it. The classical Frechet distance between two polygonal curves corresponds to the maximum distance between two point objects that traverse the curves with arbitrary non-negative speeds. Here, we consider a problem instance in which the speed of traversal along each segment of the curves is restricted to be within a specified range. We provide an efficient algorithm that decides in O(n2 log n) time whether the Frechet distance with speed limits between two polygonal curves is at most E, where n is the number of segments in the curves, and E > and equal to 0 is an input parameter. We then use our solution to this decision problem to find the exact Frechet distance with speed limits in O(n2 log2 n) time.<\/p>\n

TR-10-08.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-10-08 April 27, 2010 Frechet Distance with Speed Limits Anil Maheshwari, Jorg-Rudiger Sack, Kaveh Shahbaz, Hamid Zarrabi-Zadeh Abstract In this paper, we introduce a new generalization of the well-known Frechet distance between two polygonal curves, and provide an efficient algorithm for computing it. The classical Frechet distance between two polygonal curves […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12468,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13325","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13325","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13325"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13325\/revisions"}],"predecessor-version":[{"id":13326,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13325\/revisions\/13326"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12468"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13325"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13325"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}