Search

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.2 introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R1, specified by linear interpolation in a sequence of τ time stamps, we show that all maximal groups can be computed in O(τ2n4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of α(n) in the running time, where α denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in O(τ2n5logn) time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not. We also show that one τ factor can be traded for a much higher dependence on n by giving a O(τn42n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on nand linear dependence on τ.

An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative r is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between r and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between r and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.

We study the problem of maintaining knowledge of the locations of $n$ entities that are moving, each with some, possibly different, upper bound on their speed. We assume a setting where we can query the current location of any one entity, but this query takes a unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we wish to minimize uncertainty concerning the locations of all entities at some target time that is t units in the future. We measure uncertainty by the ply of the potential locations: the maximum over all points $x$ of the number of entities that could potentially be at $x$. Since the ply could be large for every query strategy, we analyze the performance of our query strategy in a competitive framework: we consider the worst-case ratio of the ply achieved by our strategy to the intrinsic ply (the smallest ply achievable by any strategy, even one that knows in advance the full trajectories of all entities). We describe an efficient strategy that, knowing only an upper bound on the speed of individual entities, is $O(k)$-competitive, provided the lead time t is at least 2n and the number of different entity speed classes (groups of entities whose speed bounds differ by at most a factor of two) is at most $k$. (This contrasts with the fact that, even given the full trajectories, the problem of computing the intrinsic ply is NP-hard.) If t is small, though at least $n$, and the entities move in any constant dimension $d$, our strategy is $O(k(\frac{\widetilde{T}}{n})^{d-\frac{d}{d+1}})$-competitive, where $\widetilde{T}$ is the median of the lengths of time since the $n$ entity locations were last known precisely. Matching lower bounds demonstrate that our strategy, in all cases, is optimally competitive, up to constant factors. Read More: http://epubs.siam.org/doi/10.1137/15M1031217

Technology such as the Global Positing System (GPS) has made tracking moving entities easy and cheap. As a result there is a large amount of trajectory data available, and an increasing demand on tools and techniques to analyze such data. We consider several analysis tasks for trajectory data, and develop efficient algorithms to perform them automatically. In particular, we study the following tasks: •Find a segmentation of a trajectory based on a non-monotone criterion. •Find hotspots; regions in which the entity spent a large amount of time. •Find all groups and the grouping structure. A group is a movement pattern in which sufficiently many entities move together during a sufficiently long time interval. In addition to the groups themselves we also find the relation between groups, e.g. a large group came into existence when two smaller groups merged. •Find a central trajectory: a representative for a set of trajectories. For each task, we formalize the problem, and analyze its geometric properties. We use these properties to obtain efficient algorithms to automatically perform the task at hand. In many cases, we also show that our analysis is tight, and that our algorithms are optimal.

In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly ", where " is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with τ vertices each we give an O(τn2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(τ (n2 + mλ4(n))) upper bound, where m is the total complexity of the obstacles, and λs(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(τ min{n2 + m3λ4(n), n2m2}) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.

In a recent paper [2] we gave query strategies for minimizing the ply of the potential locations of a set of moving entities. We extend our results to the case where the entities have dierent maximum speeds. We present a query strategy that can achieve ply O(k) when we have at least 2n time, the intrinsic ply of the entities is , and the speeds of the entities fall into k speed classes. Furthermore, we show that for every query strategy there is a set of n entities for which the strategy achieves ply (k). Hence, our results are optimal up to a constant factor. We present our query strategy for entities moving in R1. However, our results extend to higher dimensions.

To alleviate the problem that only a single polygonal line can be drawn to solve the puzzle, we allow interruptions by using two point symbols instead of just one. If the label of a dot is a normal number, then the edge to the next highernumbered point should be drawn, but if the label has a “+” appended to it, then the next edge should not be drawn. In this way the puzzler draws several polygonal lines. By giving a point more than one label, junctions can be made as well. ∗Department of Computing and Information Sciences, Utrecht University; Utrecht, the Netherlands; m.kaiser@students.uu.nl, {timvankapel,gerwin.klappe}@gmail.com, {m.j.vankreveld,m.loffler,f.staals}@uu.nl. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for thirdparty components of this work must be honored. For all other uses, contact the Owner/Author.

Introduction. In recent years there has been an increase in locationaware devices and wireless communication networks. This has led to a large amount of trajectory data capturing the movement of animals, vehicles, and people. The increase in trajectory data goes hand in hand with an increasing demand for techniques and tools to analyze them, for example, in transportation sciences, sports, ecology, and social services. An important task is the analysis of movement patterns. In particular, given a set of moving entities we wish to determine when and which subsets of entities travel together. When a sufficiently large set of entities travels together for a sufficiently long time, we call such a set a group. Groups may start, end, split and merge with other groups. Apart from the question what the current groups are, we also want to know which splits and merges led to the current groups, when they happened, and which groups they involved. We wish to capture this group change information in a model that we call the trajectory grouping structure.

We introduce a variation of unit-distance graphs which we call emph clear unit-distance graphs. They require the pairwise distances of the representing points to be either exactly 1 or not close to 1. We discuss properties and applications of clear unit-distance graphs.