We introduce a measure for computing the similarity between multiple polylines and a polygon, that can be computed in O(km 2 n 2) time with a straightforward dynamic programming algorithm. We then present a novel fast algorithm that runs in time O(kmn logmn). Here, m denotes the number of vertices in the polygon, and n is the total number of vertices in the k polylines that are matched against the polygon. The effectiveness of the similarity measure has been demonstrated in a part-based retrieval application with known ground-truth.
|Title of host publication||Algorithms and computation : 16th international symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings|
|Editors||X. Deng, D. Du|
|Place of Publication||Berlin|
|Publication status||Published - 2005|
|Name||Lecture Notes in Computer Science|