## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 262-283 |

Number of pages | 22 |

Journal | Journal of Algorithms |

Volume | 49 |

Issue number | 2 |

DOIs | |

State | Published - Nov 2003 |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics