An important data source for traffic analysis is GPS trajectory data. However, due to measurement inaccuracies, such data does not necessarily align well with data describing the road network. Hence, GPS data typically needs to be aligned with the road network before further analysis can take place; this process is called map matching. The challenges in map matching are exacerbated when trajectories are sparse (have a low measurement frequency); we then need to fill the gaps between the measurements with a realistic estimate of the actual route between two points. As vehicle movement is subject to physical constraints (such as acceleration and speed bounds), an estimated route should be physically consistent. We present a method that creates physically consistent estimated routes to perform map matching for sparse trajectories.

Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.

Understanding human mobility patterns is an important aspect of traffic analysis and urban planning. Trajectory data provide detailed views on specific routes, but typically do not capture all traffic. On the other hand, loop detectors built into the road network capture all traffic flow at specific locations, but provide no information on the individual routes. Given a set of loop-detector measurements as well as a (small) set of representative trajectories, our goal is to investigate how one can effectively combine these two partial data sources to create a more complete picture of the underlying mobility patterns. Specifically, we want to reconstruct a realistic set of routes from the loop-detector data, using the given trajectories as representatives of typical behavior.

We present a novel linear subdivision scheme for face-based tangent directional fields on triangle meshes. Our subdivision scheme is based on a novel coordinate-free representation of directional fields as halfedge-based scalar quantities, bridging the mixed finite-element representation with discrete exterior calculus. By commuting with differential operators, our subdivision is structure preserving: it reproduces curl-free fields precisely and reproduces divergence-free fields in the weak sense. Moreover, our subdivision scheme directly extends to directional fields with several vectors per face by working on the branched covering space. Finally, we demonstrate how our scheme can be applied to directional-field design, advection, and robust earth mover’s distance computation, for efficient and robust computation.

We present a weighted sampling strategy for distributing a system of taxi agents on a road network. We consider a setting, in which each agent operates independently, following a prescribed strategy based on historical data. Furthermore, customer requests appear dynamically and are assigned to the closest unoccupied taxi agent.

Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n log n log2 k) time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk) time algorithm for any model where consistency is "concatenable": a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models which are not concatenable. We show how to compute the maximum subsequence for such models in O(nk2 log k) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets.