AF: Small: Geometric Algorithms for Constructing Road Networks from Trajectories

该项目的目标是开发具有质量和性能保证的几何算法，用于从地理参考轨迹数据构建道路网。这是一种新型的几何重建问题，其任务是提取由一组受噪声、运动约束的轨迹采样而成的底层几何结构。将研究不同的轨道模型和公路网模型。几何形状匹配、概率建模和轨迹聚类的思想将被应用于开发具有质量和性能保证的几何算法，以利用输入轨迹的连续性。将开发概念验证实施，以在真实数据上测试和验证算法。由于全球定位系统(GPS)等定位技术的无处不在，大量的地理参考轨迹数据正在收集中。该项目将有助于解决分析这些数据这一非常及时的挑战。它还将为数字街道地图的构建和维护提供新的算法，数字街道地图是当今社会最宝贵的数字数据资源之一。该项目的结果将使大量的应用受益，从街道地图上的各种基于位置的服务到分析跟踪数据以生成徒步旅行轨迹地图或研究动物的社会行为。学生将紧密融入研究项目，为他们提供协作研究体验。

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.