Matching planar maps

Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk

Research output: Contribution to journalArticlepeer-review

126 Scopus citations


The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc. More precisely, we define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well-known Fréchet distance for curves. We first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, H and G, are geometric graphs.

Original languageEnglish (US)
Pages (from-to)262-283
Number of pages22
JournalJournal of Algorithms
Issue number2
StatePublished - Nov 2003

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Matching planar maps'. Together they form a unique fingerprint.

Cite this