Name
Abstract | ||
|---|---|---|
Let $\mathcal{N}$ and $\mathcal{M}$ be two road networks represented in vector form and covering rectangular areas Rand R驴, respectively, not necessarily parallel to each other, but with R驴 驴 R. We assume that $\mathcal{N}$ and $\mathcal{M}$ use different coordinate systems at (possibly) different, but known scales. Let $\mathcal{B}$ and $\mathcal{A}$ denote sets of "prominent" road points (e.g., intersections) associated with $\mathcal{N}$ and $\mathcal{M}$, respectively. The positions of road points on both sets may contain a certain amount of "noise" due to errors and the finite precision of measurements. We propose an algorithm for determining approximate matches, in terms of the bottleneckdistance, between $\mathcal{A}$ and a subset $\mathcal{B}'$ of $\mathcal{B}$. We consider the characteristics of the problem in order to achieve a high degree of efficiency. At the same time, so as not to compromise the usability of the algorithm, we keep the complexity required for the data as low as possible. As the algorithm that guarantees to find a possible match is expensive due to the inherent complexity of the problem, we propose a lossless filteringalgorithm that yields a collection of candidate regions that contain a subset Sof $\mathcal{B}$ such that $\mathcal{A}$ maymatch a subset $\mathcal{B}'$ of S. Then we find possible approximate matchings between $\mathcal{A}$ and subsets of Susing the matching algorithm. We have implemented the proposed algorithm and report results that show the efficiency of our approach. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-87473-7_3 | GIScience |
Keywords | Field | DocType |
subset sof,road network,matching algorithm,possible match,approximate match,road point,noisy road network matching,inherent complexity,rand r,possible approximate matchings,proposed algorithm,coordinate system | Coordinate system,Discrete mathematics,Rigid motion,Combinatorics,Road networks,Blossom algorithm,Mathematics | Conference |
Volume | ISSN | Citations |
5266 | 0302-9743 | 3 |
PageRank | References | Authors |
0.39 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yago Diez | 1 | 45 | 11.50 |
| Mario A. Lopez | 2 | 819 | 110.78 |
| J. Antoni Sellarès | 3 | 49 | 8.79 |