The objective of this project is to develop geometric algorithms with quality and performance guarantees for constructing road networks from geo-referenced trajectory data. This is a new type of geometric reconstruction problem in which the task is to extract the underlying geometric structure sampled by a a set of noisy, movement-constrained trajectories. Different models for trajectories and for road networks will be investigated. Ideas from geometric shape matching, probabilistic modeling, and trajectory clustering will be applied to develop geometric algorithms with quality and performance guarantees that exploit the continuity of the input trajectories. Proof-of-concept implementations will be developed to test and validate the algorithms on real data.
Vast amounts of geo-referenced trajectory data are being collected due to the ubiquitous availability of positioning technologies such as the Global Positioning System (GPS). This project will help address the very timely challenge of analyzing this data. It will also provide novel algorithms for construction and maintenance of digital street maps, which are among the most valuable digital data resource in today's society. The results of this project will benefit a wealth of applications ranging from a variety of location-based services on street maps to the analysis of tracking data for hiking trail map generation or for studying social behavior in animals. Students will be tightly integrated into research projects, providing them with collaborative research experience.
