Content area
This dissertation presents the latest research on enhancing the roadmap update process utilizing GPS trajectories, leveraging the widespread availability of GPS data to improve roadmap accuracy at a reduced cost. Our journey begins with map construction in Chapter 2, where we utilize GPS data from vehicles or pedestrians to create roadmaps, particularly essential for areas like hiking trails where alternative data sources, such as satellite imagery, are limited. We optimize an existing map construction method based on Fréchet clustering, making it more efficient and accurate. Our overarching objective is to identify and preserve as many geometric and topological features as possible throughout the entire process.
In Chapter 3, we assess our results by refining the graph sampling method, the prevailing approach for evaluating reconstructed maps which has often been misunderstood in the literature. We propose its application for comparing entire roadmaps and highlight its limitations. To overcome these shortcomings, we explore a novel approach based on Fréchet distance in Chapter 4, offering a continuous alternative called Length-Sensitive Fréchet Similarity (LSFS). We introduce the concept of LSFS and demonstrate that it belongs to the NP-hard class of problems when applied to graphs. Nevertheless, we propose an efficient polynomial-time algorithm for solving LSFS on polygonal curves such as GPS trajectories.
Finally, in Chapter 5, we discuss map conflation, the final stage of our map update pipeline. We introduce a graph sampling-based method for merging two road maps, identifying and integrating new segments missing from the base map.