Abstract

The challenge of map construction involves creating a representation of a travel network using data from the paths traveled by entities within the network. Although numerous algorithms for constructing maps can effectively piece together the overall layout of a network, accurately capturing smaller details like the positions of intersections and turns tends to be more difficult. This difficulty is especially pronounced when the data is noisy or collected at irregular intervals. In this paper we present Roadster, a map construction system that combines efficient cluster computation and a sophisticated method to construct a map from a set of such clusters. First, edges are extracted by producing a number of subtrajectory clusters, of varying widths, which naturally correspond to paths in the network. Second, representative paths are extracted from the candidate clusters. The geometry of each representative path is improved in a process involving several stages, that leads to map edges. The rich information obtained from the clustering process is also used to compute map vertices, and to finally connect them using map edges. An experimental evaluation of Roadster, using vehicle and hiking GPS data, shows that the system can produce maps of higher quality than previous methods.

Corresponding Publications

Improved Algorithms for Subtrajectory Clustering and Map Construction

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Jorren Hendriks, Roel Jacobs, Erfan Hosseini Sereshgi, Rodrigo I. Silveira, Jorrick Sleijster, Frank Staals, Carola Wenk

Journal of Computational Geometry, 2025

Download Local Copy View Slides Export Citation

@article{mapconstruction2025,
  author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and
                 Hendriks, Jorren and Jacobs, Roel and Hosseini Sereshgi, Erfan
                 and I. Silveira, Rodrigo and Sleijster, Jorrick and Staals, Frank and
                  Wenk, Carola},
  title = {Improved Algorithms for Subtrajectory Clustering and Map Construction},
  journal = {Journal of Computational Geometry},
  keywords = {trajectory, moving entity, geometric algorithms},
  category = {trajectories},
  volume = {196},
  year = {2025},
  numpages = {32},
  doi = {10.1016/j.cageo.2024.105845},
  url = {https://doi.org/10.1016/j.cageo.2024.105845},
}