Multiple polyline to polygon matching

M. Tanase, R.C. Veltkamp, H.J. Haverkort

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithms and computation : 16th international symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings
EditorsX. Deng, D. Du
Place of PublicationBerlin
ISBN (Print)3-540-30935-7
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Multiple polyline to polygon matching'. Together they form a unique fingerprint.

Cite this