Article

Matching planar maps

Authors:

Helmut Alt,

Alon Efrat,

Günter Rote,

Carola WenkAuthors Info & Claims

SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 589 - 598

Published: 12 January 2003 Publication History

Get Access

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 will 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 will 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 will give an algorithm for the general case where both, H and G, are geometric graphs.

References

[1]

H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5:75--91, 1995.

Google Scholar

[2]

R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200--208, 1987.

Digital Library

Google Scholar

[3]

Dan Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.

Digital Library

Google Scholar

[4]

D.S. Hirschberg. Algorithms for the longest common subsequence problem. J. ACM, 24:664--675, 1977.

Digital Library

Google Scholar

Cited By

View all

Mohamed RAly HYoussef M(2017)Accurate Real-time Map Matching for Challenging EnvironmentsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.259195818:4(847-857)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TITS.2016.2591958
Aly HYoussef MAli MHuang YGertz MRenz MSankaranarayanan J(2015)semMatchProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820824(1-10)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2820783.2820824
Wang GZimmermann RDemiryurek USarwat M(2014)Spatial sensor data processing and analysis for mobile media applicationsProceedings of the 1st ACM SIGSPATIAL PhD Workshop10.1145/2694859.2694868(1-5)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2694859.2694868
Show More Cited By

Index Terms

Matching planar maps
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

Matching planar maps

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 ...
Planar G² transition with a fair Pythagorean hodograph quintic curve

Recently planar cubic and Pythagorean hodograph quintic transition curves that are suitable for G² blending were developed. They are suitable for blending, e.g. rounding corners, or for smooth transition between two curves, e.g. two circular arcs. It ...
Comparison of Distance Measures for Planar Curves

The Hausdorff distance is a very natural and straightforward distance measure for comparing geometric shapes like curves or other compact sets. Unfortunately, it is not an appropriate distance measure in some cases. For this reason, the Fréchet distance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

January 2003

891 pages

ISBN:0898715385

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 12 January 2003

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
479
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mohamed RAly HYoussef M(2017)Accurate Real-time Map Matching for Challenging EnvironmentsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.259195818:4(847-857)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TITS.2016.2591958
Aly HYoussef MAli MHuang YGertz MRenz MSankaranarayanan J(2015)semMatchProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820824(1-10)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2820783.2820824
Wang GZimmermann RDemiryurek USarwat M(2014)Spatial sensor data processing and analysis for mobile media applicationsProceedings of the 1st ACM SIGSPATIAL PhD Workshop10.1145/2694859.2694868(1-5)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2694859.2694868
Wang GZimmermann RHuang YSchneider MGertz MKrumm JSankaranarayanan J(2014)EddyProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666383(33-42)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2666310.2666383
Shang SLu HPedersen TXie X(2013)Finding Traffic-Aware Fastest Paths in Spatial NetworksProceedings of the 13th International Symposium on Advances in Spatial and Temporal Databases - Volume 809810.5555/2960717.2960727(128-145)Online publication date: 21-Aug-2013
https://dl.acm.org/doi/10.5555/2960717.2960727
Shang SDing RYuan BXie KZheng KKalnis P(2012)User oriented trajectory search for trip recommendationProceedings of the 15th International Conference on Extending Database Technology10.1145/2247596.2247616(156-167)Online publication date: 27-Mar-2012
https://dl.acm.org/doi/10.1145/2247596.2247616
Fang SZimmermann R(2011)EnAcqProceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2093973.2094004(221-230)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2093973.2094004
Shang SYuan BDeng KXie KZhou X(2011)Finding the most accessible locationsProceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2093973.2093999(181-190)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2093973.2093999
Griffin THuang YSeals SLiao L(2011)Routing-based map matching for extracting routes from GPS trajectoriesProceedings of the 2nd International Conference on Computing for Geospatial Research & Applications10.1145/1999320.1999344(1-6)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.1145/1999320.1999344
Zheng KTrajcevski GZhou XScheuermann P(2011)Probabilistic range queries for uncertain trajectories on road networksProceedings of the 14th International Conference on Extending Database Technology10.1145/1951365.1951400(283-294)Online publication date: 21-Mar-2011
https://dl.acm.org/doi/10.1145/1951365.1951400
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Matching planar maps

Planar G² transition with a fair Pythagorean hodograph quintic curve

Comparison of Distance Measures for Planar Curves