2014/09/16 by Schlesinger, M. I., Vodolazskiy, E. V., Yakovenko, V. M.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1409.4613
The article analyzes similarity of closed polygonal curves in Frechet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm that determines whether the Frechet distance between two closed polygonal curves with m and n vertices is less than a given number is described. The described algorithm takes O(mn) time whereas the previously known algorithms take O(mn log(mn)) time.