In recent years, with the rapid growth in the amount of publicly available Volunteered Geographic Information (VGI) data, automatic map generation from GPS trajectories has attracted great attention. Maps generated from these data can for example complement commercial maps in less developed areas. Two main challenges in the automatic generation of maps from volunteered GPS data are the handling of noise and of non-homogeneous sampling of road segments (for example, roads in downtown area can receive significantly more GPS traces than roads in residential areas). In this paper, we present a novel framework for map reconstruction based on a topological idea: the Morse theory. In particular, the use of Morse theory and topological simplification allows us to handle the issues of both noise and non-homogeneous sampling in an elegant unified framework. Our algorithm is significantly simpler than previous approaches, both conceptually and implementation speaking. Little pre- and post-processing is required, and yet the algorithm can reconstruct robust road-networks from challenging data sets (such as GPS traces for Berlin or Beijing cities) that are comparable or better than the output of previous state-of-the-art approaches. The new algorithm is also orders of magnitude faster than previous approaches on large data sets (for example, the entire processing of the Berlin city data with about 27189 trajectories takes less than one minute).

Let f be a continuous function defined on a topological space. As we increase the function value, connected components in the level set of f appear, disappear, merge, or split, and the Reeb graph tracks these changes. The join and split trees of f track the changes of connected components in the sublevel and superlevel set respectively. If the Reeb graph is loop-free, then it is a tree called the contour tree. Given a piecewise linear function f defined on a simplicial complex K, Carr, Snoeyink and Axen proposed a simple and elegant algorithm to compute the contour tree of f by "merging" its join and split trees in near-linear time.