Segmenting Trajectories: A Framework and Algorithms Using Spatiotemporal Criteria
Segmenting Trajectories: A Framework and Algorithms Using Spatiotemporal Criteria
Segmenting Trajectories: A Framework and Algorithms Using Spatiotemporal Criteria
R ESEARCH A RTICLE
Segmenting trajectories:
A framework and algorithms using
spatiotemporal criteria∗
Maike Buchin1, Anne Driemel2, Marc van Kreveld3, and
Vera Sacristán4
1
Dept. of Mathematics and Computer Science, TU Eindhoven, The Netherlands
2
Dept. of Information and Computing Sciences, Utrecht University, The Netherlands
3
Dept. of Information and Computing Sciences, Utrecht University, The Netherlands
4
Dept. de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Spain
Received: July 19, 2011; returned: October 10, 2011; revised: November 16, 2011; accepted: December 10, 2011.
Abstract: In this paper we address the problem of segmenting a trajectory based on spa-
tiotemporal criteria. We require that each segment is homogeneous in the sense that a set
of spatiotemporal criteria are fulfilled. We define different such criteria, including location,
heading, speed, velocity, curvature, sinuosity, curviness, and shape. We present an algo-
rithmic framework that allows us to segment any trajectory into a minimum number of
segments under any of these criteria, or any combination of these criteria. In this frame-
work, a segmentation can generally be computed in O(n log n) time, where n is the number
of edges of the trajectory to be segmented. We also discuss the robustness of our approach.
1 Introduction
Due to technologies such as GPS tags, trajectories are collected on a large scale. A trajec-
tory represents the locations of a moving object over a certain time interval. Typically, a
trajectory is collected by recording the location at a number of moments in time. Such a
∗ This article is a revised and expanded version of a paper that appeared at ACM SIGSPATIAL 2010 [9].
c by the author(s) Licensed under Creative Commons Attribution 3.0 License
CC
34 B UCHIN , D RIEMEL , VAN K REVELD , S ACRIST ÁN
sequence of points with time stamps can then be interpreted as a continuous motion path
of a moving object by some form of interpolation. The recording of locations can be done
at regular or irregular intervals. Due to noise in the GPS data certain locations can be un-
reliable or missing. In some applications the recording is speed-dependent, with higher
sampling rates if the moving object is faster.
With the existence of large collections of trajectory data, the analysis of such data has
also taken a flight. Examples are detecting flocking behavior in trajectories of animals [7],
analyzing the trajectories of several shoppers in a supermarket [25], and determining com-
muting patterns in the trajectories of people [8].
The analysis task we discuss in this paper is segmenting a trajectory. The segmentation
problem for a trajectory is to partition it into a (typically small) number of pieces, which
are called segments. (Note that segment refers to subtrajectory and not the mathematical line
segment.) The idea of segmentation is to obtain segments where movement characteristics
inside each segment are uniform in some sense. Movement characteristics are for example,
speed, heading, or curviness, or any combination of such characteristics. Segmentation
aids in understanding the behavior of animals from animal trajectories, it helps to find and
analyze patterns in movement of sports players, and is important for content-based motion
retrieval tasks.
end
start
Figure 1: A trajectory and three segmentations of it: cutting points are indicated by squares.
Figure 1 illustrates the segmentation problem using different criteria. To the top left, a
possible trajectory is given, based on points sampled with equal time intervals. This means
that the length of each edge is proportional to the (average) speed along that edge. The
heading along an edge is the direction from the earlier endpoint to the later endpoint. To
the top right, a segmentation is shown where the criterion is that within each segment, the
speed cannot differ more than a factor 2. Hence, a segment cannot contain two edges of
which one is more than twice as long as the other. To the bottom left, a segmentation by
heading is shown, where the criterion is that within each segment, the direction of motion
differs by at most 90◦ . To the bottom right, a segmentation is shown where both criteria are
used in conjunction. In all three segmentations, the number of segments used is minimum
(3 for speed, 5 for heading, and 6 for speed and heading simultaneously).
www.josis.org
S EGMENTING T RAJECTORIES 35
Related work Segmentation is generally understood as the partitioning of data into ho-
mogeneous, possibly meaningful pieces. This is true for segmentation in image process-
ing [16, 34] and DNA sequence segmentation [6], for instance. In image processing, seg-
mentation is the partitioning of a digital image into regions of pixels by similarity in color
and intensity. These regions are often meaningful parts of the image, and therefore seg-
mentation can help in image analysis.
Segmentation is also common in time-series analysis [2, 10, 19]. Again the objective is
to partition the data into homogeneous pieces. The objective may be for compact or high-
level representation, for reduction of noise, and eventually for understanding or prediction
of the behavior of the time-series data. These papers treat segmentation as a simplification
or clustering problem, where a segment basically is a continuous section of the time series
(the trajectory) that could be replaced by a single edge or median point in the resulting
segmentation. The choice of the error criterion determines in which sense the characteris-
tics of the input are kept. It is also common to assume that the number of segments to be
used is given, and a global error function should be optimized [27, 35]. The most common
techniques used for segmentation of time-series data include curve fitting [27], dynamic
programming [22, 35], and various heuristics [2, 40]. The running time is generally O(n2 k),
where n is the length of the time series and k is the maximal number of segments in the
output, see also [3].
For the processing of geographic trajectories of moving objects, segmentation has also
been studied [15, 40]. The objectives are generally the same as for time-series data seg-
mentation. Some papers discuss segmentation of trajectories for the purpose of high-level
representation, or semantic annotation [19, 42]. Here the goal is it also to have as much
homogeneity within each segment as possible while using only few segments in total. Al-
ternatively, a given set of templates are used to match to parts of the trajectory to realize
semantic annotation. These papers focus more on the semantics of spatiotemporal trajecto-
ries.
on the application domain and the exact problem at hand. We mention a few application
scenarios that we consider relevant to our setting.
Bird ecologists study recurrent patterns and behavioral changes in animal tracking data
to explain the individual’s behavior during foraging or migration [18, 37]. It is common
to split and annotate the trajectories into distinct segments, depending on the birds activ-
ity, e.g., directional flight, soaring, circling, etc. Often, this task is performed manually
by a domain expert, but the process could be automated using a segmentation algorithm,
given a formal definition of these activity states, as in [36] for example. In fact, a com-
mon approach in animal movement analysis assumes that the individual movement is a
response to a combination of internal states, physiological constraints, and environmental
factors [18, 23, 24], which can be modeled using a state-space framework [30]. For many
models, the information that defines a particular state will be encoded in the spatiotem-
poral trajectory or is available through context data. The different states of a process can
be defined manually using domain knowledge, or sometimes they can be identified using
cluster analysis [37].
State-space models are an important tool used in many research areas. Scientists study
the trajectories generated by such a model to find out more about the underlying dynamic
system. In order to simplify this analysis, the trajectories are sometimes preprocessed into
semantic label sequences, a technique which is called symbolic time-series analysis [33,39].
We think that segmentation can help in this analysis by producing more sophisticated label
sequences.
Another application is the task of context recognition for mobile phone applications.
Modern mobile devices carry sensors for acceleration, noise level, luminosity, humidity,
etc. Online segmentation algorithms for the time series composed of this data can help to
adapt the user interface and increase the usability [22].
Finally, the solutions to the segmentation problem described in this paper can be used to
detect outliers. An outlier can be considered noise or relevant information. In both cases it
is desirable to detect it in a trajectory. An outlier can (arguably) be defined as a short section
on the trajectory that represents a behavior which deviates from its context, i.e., before and
after this section. If we can identify certain attributes which have to be homogeneous along
the noise-free parts of the trajectory, then segmentation based on these attributes will reveal
the outliers as very short segments.
www.josis.org
S EGMENTING T RAJECTORIES 37
In Section 6 we consider more complex attributes like curvature, sinuosity, and curviness,
and possible criteria for them. We will show that segmenting optimally and efficiently
on these criteria is possible as well, with the same approach. In Section 7 we show that
shape-fitting criteria can also be used in our framework. These criteria do not result in
homogeneity of some attribute value within each segment, but achieve homogeneity in a
different manner. In Section 8 we discuss robustness in relation to segmentation, and show
that it can be handled on different levels.
Additional material in this version Part of this work has been published previously in
a conference proceedings version, see [9]. The additional material provided in the current
version can be summarized as follows. We included sections which were previously omit-
ted due to space requirements and we give full proofs to all the claims that were posed in
the previous version together with an extended discussion at several places. In particular,
the paragraph on application areas in Section 1 has been added in this version and a sec-
tion on robustness, see Section 8. We give mathematical formulations of different ways to
combine criteria and show how they can be integrated in the framework, see Section 5.4.
Furthermore, we discuss a completely new type of criterion based on shape in Section 7.
2 Preliminaries
We define two types of trajectories, discrete and continuous (piecewise-linear). In both
cases, the representation of the trajectory usually follows from the way it is collected: a dis-
crete sample of time-space positions. A piecewise-linear trajectory is a continuous motion
path, while a discrete trajectory is defined only at a series of discrete points in time.
Note that a subtrajectory of a discrete trajectory is a discrete trajectory itself, and the
same holds true for a piecewise-linear trajectory.
For a discrete trajectory one does not wish to assume any location between the known,
measured locations at the time stamps t0 , . . . , tn . This may be due to under-sampling of the
trajectory: locations would be unreliable and therefore not so useful. In practice this can
happen, for example, when tracking migrating birds over long distances and time stretches.
It is common practice to choose a very low tracking frequency in case of a limited energy
supply of the tracking devices, which are carried by the birds.
www.josis.org
S EGMENTING T RAJECTORIES 39
Observe that using absolute boundary values, like 10 km/h, 20 km/h, 50 km/h, and
100 km/h for speed might lead to oversegmentation. Using these absolute values a trajec-
tory that has speeds 51–51–98–98–103–103 km/h along its edges is segmented into more
pieces than desired. Also, it would segment a trajectory with speeds 49–51–49–51 km/h
along its edges into four segments. Hence, we will only use criteria based on relative values
within a segment in this paper.
Another illustrative example can be given using the location attribute. An absolute
criterion for location would categorize the positions of the trajectory into zones with fixed
boundaries. One of the known issues with this approach is the so-called modifiable area
unit problem (MAUP) [12]. A relative criterion is described in Section 3. Here, we say the
criterion is satisfied for a given subtrajectory, if the positions on this subtrajectory fit into
any disk of a given radius, which can be centered anywhere in space.
Heading The heading at any moment in time is the direction in which the moving object
is traveling at that moment. It can be specified by an angle in the range [0, 2π) according to
some reference system, or it is UNDEFINED if the object is not moving. For example, purely
north has angle 0 and purely east has angle +π/2. For trajectories represented by vertices
and edges, the heading has a straightforward definition on each edge, but not at vertices.
To define heading at a vertex, we can for instance choose it to be the same as the heading on
the edge just before or after the vertex. We should choose it to make sure that no segment
consists of a single vertex.
A straightforward criterion for heading is that in each segment, the heading lies within
an angular range of some pre-specified size α, or it is UNDEFINED. In other words, for each
segment, all of its edges have length zero and the heading is UNDEFINED, or there exists an
angle β such that all edges in the segment have angles in the range [β, β + α]. This range
should be interpreted modulo 2π, as heading has a circular scale. The angle α must be
chosen smaller than π; a reasonable value might be π/3 but it depends on the application.
This angular range criterion for heading is monotone.
Speed The speed at any moment in time is well-defined on any edge since we assume
constant speed on any edge. At any vertex, the speed can be chosen the same as the speed
on the edge just before or after the vertex. A straightforward criterion for speed is that on
any segment, the difference (or ratio) of the maximum and minimum speed is at most some
given value. This difference criterion for speed (or ratio criterion for speed) is monotone.
Velocity The velocity at any location on τ is captured by a vector whose length is speed
and whose direction is heading. Previously we bounded speed and heading separately,
but we can also define a criterion directly on velocity. To this end, consider the velocity
vector plane, where any point p represents the vector from the origin O to p. The origin O
represents the null vector. Since all points on any single edge of τ have the same velocity,
they are represented by the same point in the velocity vector plane.
Let α be some fixed angle in [0, π] that is specified by the criterion. An α-wedge is a
wedge whose apex is at O and that has opening angle α in the velocity vector plane. The
disk criterion for velocity specifies that there exists a disk inside an α-wedge such that for
each segment of the segmentation and for any location on an edge in that segment, its
velocity vector has its representing point in that disk. Note that if the representing points
www.josis.org
S EGMENTING T RAJECTORIES 41
fit in a disk that lies inside a wedge of opening angle α, we can always enlarge the disk to
be tangent to the bounding rays of the wedge and keep the points representing the velocity
vectors inside.
The criterion is quite similar to the angular range criterion for heading combined with
the ratio criterion for speed using a conjunction, for which the shape is a sector of an an-
nulus centered at O in the velocity vector plane. We include it to show that our framework
can handle a variation like this as well. Figure 2 illustrates the two criteria.
O α O α
(a) (b)
Figure 2: The points represent velocity vectors starting at O. (a) Speed and heading are
bounded independently. (b) Speed and heading are bounded in conjunction with the disk
criterion.
4 Algorithmic framework
We show that a trajectory with n edges can be segmented optimally and in O(n log n) time
if the following conditions are fulfilled on the criterion that is used.
The first condition is necessary for the optimality of the segmentation, whereas the other
three conditions are needed for the running time. The third condition is not needed for dis-
crete segmentation and the fourth condition is trivially fulfilled for discrete segmentation.
In the extreme case that the number of segments in the output is superlinear in n, this
number will be an additional term in the running time. This will not occur in practice,
since segmentations that have more segments than the trajectory has vertices are typically
not useful.
Theorem 4. Given a trajectory τ and a monotone criterion for segmentation that should be satisfied,
a greedy strategy yields an optimal solution to the segmentation problem.
Incremental method The most simple implementation for a greedy strategy is incremen-
tal. Let ti+1 be the first vertex strictly after s, the end time of the last segment. We incre-
mentally call T EST(τ [s, ti+1 ]), T EST(τ [s, ti+2 ]), . . ., until a test fails. If this happens for the
test T EST(τ [s, tj ]), then we run F URTHEST(τ [s, tj ]). The efficiency of this implementation
depends on whether we can efficiently perform T EST(τ [s, ti+a+1 ]) if we already know that
T EST(τ [s, ti+a ]) returns true. For the monotone criteria given for heading and speed, we
can test every next vertex and edge in O(1) time and this results in a linear running time.
More generally, using this method one can segment a trajectory with n edges optimally
in time O(n) with respect to a range criterion of any single-valued attribute, if F URTHEST
takes O(m) time on a subtrajectory of m edges.
For the disk and diameter criteria for location, the attribute is not single-valued. For
an efficient incremental solution, we would need an algorithm that efficiently maintains
the diameter or smallest enclosing disk under insertions. Such an algorithm exists for the
problem of deciding whether a disk of given radius exists that contains the points, under
insertions and deletions given off-line with O(log m) update time [21], but not for the diam-
eter version. In any case, the method we describe next is simpler, equally or more efficient,
and more general.
www.josis.org
S EGMENTING T RAJECTORIES 43
a ← 1;
while ( i + a ≤ n && T EST(τ [s, ti+a ]) )
{ a ← 2a ; }
j ← Binary search in [i +
a/2, min(i + a, n)] ,
s.t. T EST(τ [s, tj−1 ]) = t r u e ∧ ( j = n ∨ T EST(τ [s, tj ]) = f a l s e ) ;
q ← F URTHEST(τ [s, tj ]) ;
Sopt ← Sopt ∪ τ [s, q] ; / / Next segment found
s ← q; i ← j −1;
}
Theorem 5. For a trajectory with n edges, if T EST takes T (m) time for a subtrajectory with m
edges and F URTHEST takes F (m) time for a subtrajectory with m edges, then optimal segmentation
takes O(T (n) log n + F (n)) time (assuming T (m) and F (m) are at least linear in m and at most
polynomial in m and the number of segments in the output is linear in n).
Proof. Suppose the optimal number of segments is h, let m1 , . . . , mh be the numbers of
edges (fully or partially) spanned by the segments which are computed by our algorithm.
Then we have hi=1 mi ≤ n + h − 1.
During the computation of one segment of unknown size m, T EST is called on subtra-
jectories that have size smaller than 2m. The number of times it is called in the while-loop
is bounded by the maximal a such that 2a ≤ 2m, i.e., a ≤ log 2m, since the test value is
doubled until it reaches the first number that is greater than m. After this, a binary search
on the interval of size at most m will perform a maximum of O(log m) calls to T EST on
subtrajectories of size smaller than 2m. Computing a segment spanning m edges therefore
takes at most O(T (2m) log m + F (m)) time. Note that F URTHEST is called only once at the
end. h
We conclude that the algorithm takes i=1 (T (2mi ) log mi + F (mi )) time in total. Since
T (m) is at least linear, T (m) log m is at least linear as well, and since F (m) is also linear,
h
i=1 (T (2mi ) log mi + F (mi )) ≤ T (n + h) log(n + h) + F (n + h). Since h = O(n) and T (m)
and F (m) are at most polynomial, we have T (n + h) log(n + h) + F (n + h) = O(T (n) log n +
F (n)).
Theorem 6. Let τ be a trajectory with n edges, and let an attribute function φ(t) be defined for
any t ∈ [t0 , tn ] by analytic functions ψ1 (t), . . . , ψk (t), with k = O(n). If for any 1 ≤ i ≤ k,
www.josis.org
S EGMENTING T RAJECTORIES 45
we can (i) evaluate ψi (t) in time O(1), (ii) compute the minima and maxima of ψi (t) over the
interval on which it is defined in time O(1), and (iii) evaluate ψi−1 (y) in time O(1), then an optimal
segmentation with respect to a range criterion of this attribute can be computed in O(n log n) time
after preprocessing.
Proof. Assumption (ii) implies that each ψi (t) has O(1) extrema in the interval on which it
is defined. We add these extrema as time stamps and vertices to τ , and note that τ still has
O(n) vertices and edges in total. Adding time stamps at the extrema of each ψi (t) causes
φ(t) to be monotone (increasing or decreasing) on each edge. The functions ψ1 (t), . . . , ψk (t)
can each be associated with O(1) consecutive edges. With this adaptation, T EST can be used
as before, and we need to evaluate φ only at vertices of τ to determine if a subtrajectory
τ [s, tj ] satisfies the range criterion of the attribute.
The routine F URTHEST(τ [s, tj ]) requires the computation of the inverse function φ−1 j
on some interval [tj−1 , tj ], to find the last moment of time up to where the segment still
satisfies the criterion. We evaluate φ at s and the vertices ti+1 , . . . , tj−1 to obtain the max-
imum and minimum values realized up to tj−1 . If function ψj is increasing, then we use
the minimum realized value on τ [s, tj−1 ] to compute the maximum allowed value Max of
ψj . The correct result of F URTHEST is the time ψj−1 (Max ). Symmetrically, if function ψj
is decreasing, then we use the maximum realized value on τ [s, tj−1 ] to compute the mini-
mum allowed value Min of ψj . The correct result of F URTHEST is the time ψj−1 (Min). By
assumption (iii), we can compute the inverse of ψj in constant time.
Now, Theorem 5 implies that optimal segmentation takes O(n log n) time after prepro-
cessing, using the same algorithm as before.
Theorem 7. An optimal segmentation using the angular range criterion for heading, and the ratio
or difference criterion for speed, can be computed in O(n log n) time for a trajectory with n edges.
pm
pm
pm − 1
pm − 1
(a) (b)
Figure 3: Optimal solution determined by (a) one point, or (b) two points. The arrow to pm
illustrates the optimization.
The pseudocode for solving the problem is given in Algorithm 2; the returned result
must be transformed back by the inverse of the affine transformation. Note the similarity
to the code for smallest enclosing disk or linear programming in constant dimensions [14].
Algorithm 2 Randomized incremental construction for F URTHEST for the disk criterion
for location.
/ / Input: A set P with m − 1 points, and a radius r
Let (p1 , . . . , pm−1 ) be the points of P in random order ;
D1 ← O PT D ISK(r, p1 ) ;
for h ← 2 to m − 1
{
i f Dh−1 contains ph
{ Dh ← Dh−1 ; }
e l s e Dh ← O PT D ISK(r, p1 , . . . , ph−1 ) with the
condition that ph is on Dh ’s boundary
}
r e t u r n the rightmost point on the x-axis and in Dm−1
Algorithm 2 uses a routine O PT D ISK which can be implemented as follows. Note that a
disk of fixed radius whose boundary contains a point ph can only pivot around this point,
and has just one degree of freedom which is angular. Every point in p1 , . . . , ph−1 restricts
the angle by some angular interval, and the common intersection of these is again an angu-
lar interval that is computed in O(m) time by a single for-loop. Over this angular interval
we can optimize the disk easily in O(1) time. Therefore, using the standard efficiency anal-
ysis for randomized incremental construction [14], Algorithm 2 takes linear expected time,
where the expectation is only over the randomization performed within the algorithm.
That is, we do not assume a certain probability distribution on the input.
Lemma 8. Given a subtrajectory τ [ti , tj ] such that vi , . . . , vj−1 fit in a disk of radius r but
vi , . . . , vj do not fit in any disk of radius r, the problem of computing a disk of radius r that contains
vi , . . . , vj−1 and the largest possible part of ej is LP-type.
Proof. We will show that the equivalent, transformed problem is an LP-type problem. Since
the radius of the disk is fixed, an optimal solution for P is already determined by up to 2
www.josis.org
S EGMENTING T RAJECTORIES 47
points of P , the basis of the problem, which shows that the combinatorial dimension of the
problem is 2. We need to show the two requirements monotonicity and locality.
Monotonicity is trivially satisfied: if a point of the set is removed, then the disk still cov-
ers the remaining points, and therefore the solution for the new problem instance cannot
be worse (meaning: less of the positive x-axis covered). To ensure locality we need to show
the following: if a point set G yields an optimal point with x-coordinate xG and a subset
F ⊂ G also yields xF = xG , then the two disks are identical. Let DG , DF be the disks cor-
responding to G and F , respectively. Assume for the sake of contradiction that DF = DG .
Clearly all points in F lie inside DF ∩ DG because both are enclosing disks. The two disks
have boundaries that pass through (xG , 0), since they have the same optimal solution. Let
q be the other intersection point of the boundaries of DF and DG . Now we can pivot DF
around q while increasing DF ∩ DG , which necessarily results in an intersection point of
the boundary of DF with the positive x-axis with higher x-coordinate, a contradiction.
Next we consider the diameter criterion for location. For any set of n points in the
plane, the diameter can be computed in O(n log n) time as follows. First, sort the points
on x-coordinate in O(n log n) time. Second, construct the convex hull of the sorted set of
points in O(n) time by a Graham scan [14]. Third, perform a rotating calipers step (visit
antipodal pairs) on the convex hull in O(n) time to find the furthest pair of points, see [32].
Hence, we can implement T EST to run in O(m log m) time on a subtrajectory of m edges.
We can implement F URTHEST to run in O(m) time. The maximum allowed diameter d
will be realized by one point among τ (s), vi+1 , . . . , vj−1 and a point on the edge ej . The de-
sired point on ej has distance exactly d to one point from τ (s), vi+1 , . . . , vj−1 and a smaller
distance to the other points. Hence, we simply compute for each point the point on the
edge ej that is at distance d. From the points on ej , we choose the one closest to vj−1 and
return it.
Theorem 9. An optimal segmentation using the disk criterion for location can be computed in
O(n log n) time for a trajectory with n edges, and using the diameter criterion in O(n log2 n) time.
Remark: We will show in Section 7 that we can also segment optimally using the diameter
criterion in O(n log n) time. This requires an extra algorithmic idea that we postpone for
now.
an α-wedge, and then we return true, or no smallest disk exists (and therefore no disk at
all), and then we return false as the result of T EST.
The following lemma describes center points of disks that contain a fixed point on their
boundary while remaining twice tangent to some α-wedge, see Figure 4(c).
p
c
d r
O
O α
O 2
(a) (b) (c)
Figure 4: (a) Computing the tangents to the minimum enclosing circle is not guaranteed to
give the wedge with smallest angle. (b) The radius r and the distance d of the circle center
to O are directly related via d sin(α/2) = r. (c) The circles pivoting at a fixed point p while
remaining tangent to an α-wedge have their center on the circle L.
Lemma 10. For any point p, the locus of the center points of disks that are twice tangent to an
α-wedge and which contain p is a disk.
Proof. For any disk inside and twice tangent to the α-wedge, denote its center by c = (c1 , c2 )
and radius by r, and let d = d(c, O). Notice that r = d sin(α/2) for all such disks, see
Figure 4(b). Hence, p = (p1 , p2 ) lies inside the disk if and only if
This is equivalent to
2 2
p1 p2 sin2 (α/2)
c1 − 2
+ c 2 − 2
≤ (p21 + p22 ) 4
cos (α/2) cos (α/2) cos (α/2)
which means that c lies inside the disk centered at the point ( cos2p(α/2)
1
, cos2p(α/2)
2
) with radius
| sin(α/2)|
2 2
(p1 + p2 ) cos2 (α/2) . See Figure 4(c) for an illustration.
Lemma 11. The problem of computing the smallest disk twice tangent to and inside an α-wedge is
LP-type.
Proof. If the velocity vector representations (points) of the edges ei , . . . , ej of the subtrajec-
tory can be covered by a disk that is twice tangent to an α-wedge, then the center point of
this disk lies in the intersection of the disks of the type described in 10. We can compute
these disks Di , . . . , Dj in O(m) time, where m = j − i + 1. The radius of a disk tangent
to a wedge of apex O and opening angle α is related to the distance d of its center to O by
d sin(α/2) = r, see Figure 4(b). Therefore, the smallest disk that covers the points and is
twice tangent to an α-wedge has its center at the point on the boundary of D1 ∩ · · · ∩ Dn
www.josis.org
S EGMENTING T RAJECTORIES 49
and is closest to O; its radius is uniquely defined by the position of its center point. A basis
either consists of one disk Di , in which case the point on the boundary of Di that is closest
to O is the center point that realizes the smallest disk, or the basis consists of two disks Di
and Dj , in which case the center point of the smallest disk is the intersection point of the
boundaries of Di and Dj that is closest to O. Therefore the basis computation is trivial, and
the combinatorial dimension of the problem is again 2.
The monotonicity criterion is trivially satisfied: the intersection of a set of disks G is still
contained in the intersection if we remove a disk Di from the set. Therefore a valid solution
for G is also a solution for G \ Di and the closest center point cannot be further from O. To
show that the locality criterion is satisfied, we argue as follows. Let F ⊂ G be a subset of
the disks in G, and assume for a contradiction that F and G define different closest center
points cF and cG that are at the same distance from O. Let R = D∈G D, then cF , cG ∈ R.
By convexity of R, the whole line segment connecting cF and cG lies in R. But then the
midpoint is in R and it is closer to O than cF and cG , a contradiction.
The lemma above immediately implies that T EST for the disk criterion for velocity can
be made to run in linear expected time. Since velocity is constant over edges of τ , we do
not need F URTHEST for this criterion. We obtain:
Theorem 12. An optimal segmentation using the disk criterion for velocity can be computed in
O(n log n) time for a trajectory with n edges.
Proof. Let Φ denote an arbitrary boolean combination criterion of the Φi . Let I be a a set of
subsets S of the index set {1, . . . , c}, such that
ΦCN F = Φi
S∈I i∈S
is the conjunctive normal form of Φ. It can be computed in constant time, since c is constant.
We first show that ΦCN F is a monotone criterion. If subtrajectory τ does not satisfy the
criterion ΦCN F , then for every S ∈ I, there must be an Φi , such that i ∈ S and τ does
not satisfy the criterion Φi . By the monotonicity of Φi , it also holds that τ does not satisfy
Φi if τ ⊆ τ . Therefore, τ does not satisfy ΦCN F . We observe that ΦCN F has constant
size, since the index set {1, . . . , c} has constant size and therefore only a constant number
of different subsets exist that are candidates for S ∈ I and furthermore, each such subset S
has constant size.
To prove the efficiency, we will argue that we can give algorithms for T EST and F UR -
THEST with respect to Φ that run in O(m) time and O(m log m) time, respectively, for a
subtrajectory of m edges. Theorem 5 then implies the claim. Recall that we required
that there is an algorithm for T EST for each of the Φi that runs in O(m) time. Let τ be
any such a subtrajectory. We invoke the test function on τ for each of the Φi . This takes
O(cm) = O(m) time. Let ai be the outcome of test for Φi . Now, the outcome of T EST
the
on τ for Φ can be determined by evaluating S∈I i∈S ai in constant time. Similarly, for
F URTHEST, given a subtrajectory τ [s, tj ] such that τ [s, tj−1 ] satisfies Φ but τ [s, tj ] does not,
we can run the respective algorithms for each of the Φi separately. This computation takes
O(cn log n) = O(n log n) time. Let the outcome be the values t1 , . . . , tc . We have that the
furthest point on the edge τ [tj−1 , tj ], such that the subtrajectory satisfies Φ, is defined by
t = maxS∈I mini∈S ti .
Another way to combine different criteria is by linear combinations. In this way, two
segmenting criteria may be combined such that less difference is allowed in one of them if
there is already a significant difference in the other one, and vice versa. For example, we
may allow a segment to have speed values different by at most 20 km/h if the heading is
constant, and also allow it to have a maximum heading difference of at most 40 degrees
if the speed is constant, by means of a linear combination of these two extremes. This
would also allow intermediate values such as a speed difference of 10 km/h and a heading
difference of 20 degrees.
Definition 15. Given a set of univariate attribute functions φ1 , . . . , φc , and real coefficients
a1 , . . . , ac , consider the function C(s, q) of a subtrajectory τ [s, q] defined as
C(s, q) := ai max (φi (t) − φi (t )).
s≤t≤q
1≤i≤c s≤t ≤q
We call the criterion that is satisfied for τ [s, q] iff C(s, q) ≤ δ, for a given threshold value δ, a linear
combination criterion.
If φ1 is speed in km/h and φ2 is heading in degrees, then the example above would use
a1 = 2, a2 = 1, and δ = 40, for the linear combination criterion.
Provided that certain computations are possible in an efficient manner on the attribute
functions to be combined and on the function C(s, q) as well, we can segment using a linear
combination criterion in O(n log n) time. For typical attribute functions, these requirements
will hold, but it must be verified for the combination of attributes to be used.
www.josis.org
S EGMENTING T RAJECTORIES 51
Theorem 16. Given a constant number of univariate attribute functions φ1 , . . . , φc , of which each
φi (t) is defined for any t ∈ [t0 , tn ] by analytic functions ψi,1 (t), . . . , ψi,ki (t), with ki = O(n). We
can compute an optimal segmentation using any linear combination criterion with respect to these
attributes in O(n log n) time for a trajectory with n edges, if the following requirements are met.
For any 1 ≤ i ≤ c and for any 1 ≤ j ≤ ki , we can
Proof. We first show that the function C(s, q) is monotone decreasing in s and monotone
increasing in q. For any 1 ≤ i ≤ c, we have
Let fi (s, q) := ai (maxs≤t≤q φi (t)−mins≤t ≤q φi (t )). Then C(s, q) = 1≤i≤c fi (s, q). For any
given values 0 < s < q < q < tn , we have that fi (s, q) ≤ fi (s, q ), since the interval [s, q ]
is a superset of the interval [s, q]. This implies that the function fi is monotone increasing
in the second parameter. Since the sum of monotone increasing functions is monotone
increasing, we also have that C(s, q) is monotone increasing in the second parameter. By a
similar argument, it follows that C(s, q) is monotone decreasing in the first parameter. As
a consequence, the linear combination criterion is monotone.
We will now describe how to apply the framework using a similar approach as the one
used in the proof of Theorem 6. For each 1 ≤ i ≤ c and 1 ≤ j ≤ ki we add the extrema of
the functions ψi,j (t) in the interval on which they are defined as time stamps and vertices
to τ . We also do this for the points where the domain of ψi,j ends and the domain of
ψi,j+1 starts. By Assumption (ii), each ψi,j (t) has O(1) extrema in the interval on which it
is defined and there are 1≤i≤c ki = O(cn) of these functions. Therefore, τ still has O(n)
vertices and edges in total. Now, the algorithm for T EST for a subtrajectory τ [s, q] with m
edges only has to determine the minimum and maximum of each attribute function φi over
the interval [s, q], which can be done in O(cm) time. Then, C(s, q) can be determined using
Equation 1 in constant time. Therefore, we can give an algorithm for T EST that runs in
O(m) time. We can also give an algorithm for F URTHEST. For this procedure, we are given
a subtrajectory τ [s, tj ] such that τ [s, tj−1 ] satisfies the criterion but τ [s, tj ] does not. On the
interval [tj−1 , tj ], we can determine an analytical representation of the function C(s, q) for
fixed s. By construction, each attribute function φi is defined by one function ψi,li over the
interval [tj−1 , tj ] and this function is either monotone increasing or monotone decreasing
over this interval. In the first case, mins≤t≤q φi (t) is constant for q ∈ [tj−1 , tj ], in the second
case this holds true for maxs≤t≤q φi (t). Let bi denote this constant. We have that over
[tj−1 , tj ], C(s, q) for fixed s, is the sum of terms of the type ai (bi − ψi,li (q)) and the type
ai (ψi,li (q) − bi ). By assumption (iii), we can evaluate the inverse of this function at value δ
in O(1) time, which gives the furthest point on the edge τ [tj−1 , tj ], such that the criterion is
satisfied. By Theorem 5, we can compute an optimal segmentation in time O(n log n).
k-Vertex neighborhood: The subtrajectory from the k-th vertex before τ (t) until the k-th
vertex after τ (t) (counting τ (t) itself only once if it is a vertex, and clipped at the start
and end of τ if necessary).
d-Space neighborhood: The subtrajectory from the location at distance d before τ (t) until
the location at distance d after τ (t) (measured along the trajectory, and clipped at the
start and end of τ if necessary).
t̂-Time neighborhood: The subtrajectory in between time t − t̂ and time t + t̂ (clipped at
the start and end of τ if necessary).
A vertex neighborhood may be appropriate only if the sampling is regular and no data is
missing, otherwise, vertex neighborhoods are not meaningful. In case τ was sampled with
regular time intervals, a time neighborhood is the continuous version of a vertex neigh-
borhood. A vertex neighborhood, however, changes abruptly at the vertices, while time
neighborhoods always change continuously.
An attribute that uses a neighborhood to define a value of the trajectory at a time t is
based on some subtrajectory of τ . Let us denote by tleft and tright the start and end times of
this subtrajectory.
Notice that for times t near t0 or tn , the times tleft or tright may lie outside the time span
of the trajectory. This may cause an attribute value to be undefined. We can solve this in
various different ways. For example, we could extrapolate the first and last edge of the
trajectory sufficiently far, or we could use t0 instead of tleft if tleft < t0 as the start of the
neighborhood, and use tn instead of tright when tright > tn as the end of the neighborhood.
www.josis.org
S EGMENTING T RAJECTORIES 53
Curvature Discrete curvature estimators have been studied widely to deal with the fact
that the standard curvature definition is not suitable for piecewise-linear curves [20, 26].
Different definitions of standard curvature exist in differential geometry which are all
equivalent. The corresponding definitions of discrete curvature are not equivalent, how-
ever. The commonly used methods for discrete curvature can be classified into three cate-
gories: those that use Gaussian smoothing, those that use curve or circle fitting, and three-
point estimators. All of these methods define the curvature at a point based on certain
points in a neighborhood of this point, implicitly or explicitly.
Three-point estimators define the curvature at a point p using the three points pleft =
τ (t ), p = τ (t), pright = τ (tright ). We now discuss three definitions of this type, as described
left
Figure 5(b):
2|(p − pleft ) × (pright − p)|
κ(p) = (3)
pright − p · p − pleft · pleft − pright
α pright
right
p p p
r
left
pleft p
(a) (b)
Figure 5: Discrete curvature by (a) turning angle, and (b) osculating circle.
Thirdly, the curvature is also the length of the second derivative vector if the curve is
parametrized by arc length. The third definition of discrete curvature takes the discrete
derivatives τ (pright ) = pright − p and τ (pright ) = (pright − p) − (p − pleft ), plugged into the
curvature formula:
τ (pright ) × τ (pright )
κ(p) = . (4)
τ (pright )3
The attribute functions ψ1 (t), . . . , ψk (t) for discrete curvature according to all three def-
initions satisfy the three requirements stated in Theorem 6. When pleft , p, and pright are on
some triple of edges, the time t defining p gives rise to a time tleft that defines pleft and
linearly depends on t. The analogous statement is true for pright . Hence, we can express the
curvature at p as an analytic function in t whose form can be stated easily. The function
has O(1) extrema on its interval that can be determined in O(1) time, it can be evaluated in
O(1) time, and its inverse can be computed in O(1) time as well. Hence we obtain:
Corollary 17. An optimal segmentation using a range criterion for discrete curvature as defined in
Equations (2), (3), or (4) using time, space or vertex neighborhoods can be computed in O(n log n)
time for a trajectory with n vertices.
Sinuosity The sinuosity of a point on a path refers to the amount of bending or winding
of the path in the neighborhood of this point. The term is used in the analysis of rivers and
coastlines [29, 31], but also to describe trajectories of moving animals [4, 5]. There appears
to be no standard definition for sinuosity. If τ = τ [tleft , tright ] is the subtrajectory that repre-
sents the neighborhood of τ (t), then some authors define the sinuosity at t as the arc length
of τ divided by τ (tleft ) − τ (tright ). We will refer to this as the detour sinuosity. Another
existing definition of sinuosity is the angular range of heading, as defined in Section 3,
divided by the arc length of τ. We will refer to this as winding sinuosity. Note that both def-
initions measure a slightly different winding behavior, as illustrated in Figure 6(a). While
winding sinuosity distinguishes the top two curves from the bottom curve, detour sinuos-
ity distinguishes the bottom two curves from the top curve. Other definitions include the
www.josis.org
S EGMENTING T RAJECTORIES 55
deviation of the edges of τ from the line segment connecting τ (tleft ) and τ (tright ). We focus
on the first two definitions and show how they can be used in our framework.
Figure 6: (a) Segments that are distinguished differently by winding and detour sinuosity.
(b) Segments that are distinguished by curviness, but not by winding or detour sinuosity.
(c) Segments that are distinguished by winding and detour sinuosity, but not by curviness.
Corollary 18. An optimal segmentation using a range criterion for winding or detour sinuosity
using time, space or vertex neighborhoods can be computed in O(n log n) time for a trajectory with
n edges.
Proof. We claim that Theorem 6 applies in each of the cases. If vertex neighborhoods are
used, the elementary functions are piecewise constant, both for winding sinuosity as well
as detour sinuosity. If we use space neighborhoods, then the arc length of τ is constant for
all τ (t). As such, the winding sinuosity at a point depends only on the directions of the se-
quence of edges covered by its neighborhood. Therefore the elementary attribute functions
are constant-valued functions in this case too. Similarly, detour sinuosity depends only on
the distance between the two endpoints of τ if we use space neighborhoods. Within the
range of one elementary attribute function these endpoints move on straight lines, and the
function of their distance can be expressed as the square-root of a polynomial of degree
two, which fulfills the conditions of Theorem 6. If we use time neighborhoods, the arc
length of τ is a linear function, since speed is constant on the edges of the trajectory. We
can apply Theorem 6 since the composition of a linear function with the discussed functions
still satisfies the conditions.
Curviness In the context of the discussed sinuosity definitions we propose another mea-
sure that captures the winding of a path near a point. Let vi , . . . , vj be the subsequence of
vertices strictly inside the neighborhood of τ (t), then we define the curviness at τ (t) as the
total angular change, divided by the arc length of the subtrajectory that is the neighborhood
of τ (t). We define total angular change as
j
|∠(vh+1 − vh , vh − vh−1 )|,
h=i
Requiring that a subtrajectory has a small distance to a line is a similar but more robust
criterion than the angular range criterion for heading. For example, if a moving object
is traveling in one direction, but due to an error one measurement is located just behind
the previous location, then segmentation by heading would require the current segment to
end, while segmentation by line fitting would not. If one requires a similarity to a circle,
this could be a robust replacement for the criteria that we described for curvature.
Surprisingly, this type of criterion is monotone and therefore we can apply our frame-
work. However, depending on the complexity of the shape and the degrees of freedom
allowed in the similarity transformation, the computations necessary for T EST and F UR -
THEST can be quite expensive. We discuss how to apply our framework in the most simple
case, where we compare the subtrajectory to a line. We show how to compute an optimal
segmentation in O(n log n) time in this case.
Definition 20. Given a subtrajectory τ and a value δ, we say that τ satisfies a line fitting crite-
rion with threshold δ if there exist two parallel lines L and M at distance δ such that any point on
τ lies below or on L and above or on M .
Note that even though we claim that this criterion is more robust, it may also have some
disadvantages. The line fitting criterion does not detect a very sharp turn of angle close to
π, for example. A significant part of the trajectory before the turn and after the turn could
be close to some line, which causes the parts before and after the turn to be in the same
segment.
Theorem 21. An optimal segmentation using a line fitting criterion can be computed in O(n log n)
time for a trajectory with n edges.
Proof. Clearly, the criterion is monotone. If there exist two parallel lines L and M of dis-
tance δ which enclose a subtrajectory τ , then these two lines also enclose any subtrajectory
of τ .
Now, we describe algorithms for T EST and F URTHEST that each run in O(m log m) time
on a subtrajectory of m edges. For T EST we can use an algorithm to compute the width of
a point set, because a subtrajectory satisfies the line fitting criterion with threshold δ if and
only if the width of its vertices is at most δ. The width can be computed using the rotating
calipers algorithm [32] after constructing the convex hull.
For F URTHEST, we are given a subtrajectory τ [s, tj ] such that τ [s, tj−1 ] satisfies the cri-
terion but τ [s, tj ] does not. We need to compute the furthest point r = τ (t) on the edge
τ [tj−1 , tj ], such that τ [s, t] satisfies the criterion. The width of a point set is always deter-
mined by three of its points: one point on one line and two points on the other line. In our
setting, r is one of these points, and the width of {τ (s), . . . , τ (tj−1 )} ∪ {r} is exactly δ. Let L
and M be the two lines that realize this situation. We have two cases, either the other two
www.josis.org
S EGMENTING T RAJECTORIES 57
L M
r τ (tj−1 )
q
τ (tj−1 )
q
r
p
L p
τ (s)
δ
L τ (s)
M δ
δ
M
(a) (b)
Figure 7: The two cases for the optimal configuration for F URTHEST using a line fitting
criterion: (a) The furthest point r shares a line with p or q. (b) The furthest point r is on the
opposite line of p and q.
points p and q lie on the same line and r on the other line, or p and q lie on different lines
and r shares the line with one of them. See Figure 7 for an example of the two cases.
In the first case it must be that p and q are consecutive vertices on the boundary of the
convex hull of τ [s, tj−1 ]. The point r is the intersection point of the edge τ [tj−1 , tj ] and the
line at distance δ from the line through p and q. There are O(m) candidate points r since
there are O(m) pairs of consecutive points on the convex hull.
In the second case points p and q must be antipodal on the convex hull of τ [s, tj−1 ]. This
means that there must be two parallel lines, one containing p and one containing q, that
contain τ [s, tj−1 ] (or, equivalently, its convex hull). It is well-known that a set of m points
has O(m) antipodal pairs and they can be computed in O(m) time by a rotating calipers
algorithm after the convex hull has been computed [32]. We test every antipodal pair p and
q and observe the following: If p and q are at distance less than δ, then they cannot be on
the lines L and M that determine the width together with point r. If p and q are at distance
greater than δ, there are exactly two pairs of lines that contain p and q and are at distance
δ from each other. We call these pairs of lines L and M , and L and M , see Figure 7(a).
Using the edges incident to p and q on the convex hull of τ [s, tj−1 ], we can test in constant
time whether τ [s, tj−1 ] lies between L and M (or L and M ). If so, we compute r as the
intersection point of τ [tj−1 , tj ] and L or M (or L or M ). Assuming the convex hull was
already computed, we handle every antipodal pair in O(1) time.
So for both cases together we get O(m) possible points r on τ [tj−1 , tj ] where we have
checked that τ [s, tj−1 ] lies in between L and M . We pick the furthest computed point on
τ [tj−1 , tj ] over all these valid configurations. This yields a running time of O(m log m) for
F URTHEST. We can apply Theorem 5, which implies that the overall computations take
O(n log2 n) time, since the number of segments will always be smaller than n with this
criterion.
We can improve the running time to O(n log n) using the following idea. Suppose we
are computing the next segment, which has m edges, and m is unknown. In the doubling
phase of the algorithm we use T EST as we described it. But as soon as T EST fails for the first
time, we use a slightly different method to find the O(m) antipodal pairs of points. Suppose
T EST fails on a subtrajectory τ (s), vi+1 , . . . , vi+a . Then we sort these a + 1 = O(m) points by
x-coordinate in O(m log m) time. Now we start the binary search phase but with a linear-
time version of T EST. Suppose we test τ (s), vi+1 , . . . , vj . We extract these points in x-sorted
order from the sorted sequence τ (s), vi+1 , . . . , vi+a in O(m) time. Then we use Graham’s
scan to compute the convex hull in O(m) time as well, and find the antipodal pairs in O(m)
time as well. We can now analyze the doubling phase and binary search phase separately
as in the proof of Theorem 5, which leads to O(m log m) time to find the maximal segment
starting at τ (s). In total we spend O(n log n) time on the segmentation.
As mentioned above, we can also define a circle-fitting criterion, which is satisfied if the
subtrajectory lies within an annulus of constant width. This criterion is also monotone, but
it is computationally more expensive. If we are interested in segmentation of a discrete
trajectory, we need an algorithm for T EST, which tests if the set of vertices spanned by
the segment lie within a constant-width annulus. Furthermore, if we restrict the outer
radius of the annulus to be fixed, the criterion is still monotone, but easier to compute.
A boolean combination of a constant number of circle-fitting criteria with different outer
radii could be used to detect subtrajectories of different curvature. Hence, we could use the
algorithm described in [13] which runs in O(m log m) time, achieving an O(n log2 n) time
for the overall segmentation algorithm.
8 Robustness
The segmentation process is sensitive to noise and outliers. It is likely that such data prob-
lems can cause additional segmentation, or segmentation in a different location. While it is
not the purpose of this paper to describe how to deal with noise and outliers successfully
in all cases, we describe three conceptually different ways that apply to different parts of
our framework. Recall that the segmentation in our framework is based on trajectories,
attributes, and criteria. We can choose to make any of these three concepts more robust,
which we describe next.
To make a trajectory more robust, we can apply outlier detection and removal, and
smoothing for dealing with noise and imprecision. Sometimes the device already takes
care of this. GPS often give coordinates that have been smoothed by Kalman filtering, for
example.
To make an attribute more robust, for example heading, we can use a neighborhood
definition for heading instead of a point-based definition. The heading is then determined
www.josis.org
S EGMENTING T RAJECTORIES 59
by the direction of the vector from the starting point of the neighborhood to the endpoint
of the neighborhood. This in essence smooths the attribute values.
To make a criterion more robust, we can allow for short durations where the criterion is
not met. These durations can be absolute or relative. For example, a more robust criterion
for speed is that within each segment of the segmentation, there is a speed s such that
95% of the time, the speed is in the interval [s − 3, s + 3] m/s. We note that although
such a definition of a criterion can be stated formally, the criterion is no longer monotone,
so our framework cannot be used directly. However, under certain assumptions on the
occurrences of outliers (similar to noise models), criteria that allow outliers and that are
monotone can be devised. Since it is beyond the scope of this paper to discuss models for
outliers, we do not discuss this possibility any further.
9 Conclusions
This paper presented a general framework that allows efficient and optimal segmentation
using various different criteria separately or in combination. Our approach to segmentation
is to specify criteria formally that should hold for any attribute within each segment of the
segmentation. The resulting algorithms segment a trajectory with n edges optimally in
O(n log n) time for many different criteria. The only requirements on the criteria posed
are monotonicity and that there exist efficient algorithms to evaluate these criteria for a
given subtrajectory. The property that makes a segmentation of a trajectory optimal in our
paper, is that it subdivides the trajectory into as few pieces as possible. This ensures that
the algorithm maximizes the length of each individual piece in a global fashion.
We comment that the framework extends directly to segmenting 3-dimensional trajec-
tories. Attributes must be defined based on 3-dimensional coordinates of vertices, and the
implementations of T EST and F URTHEST must be adapted to this end. For example, the disk
criterion for location becomes a ball criterion. Also, curvature is a more complex attribute
in 3-space, described by curvature and torsion [26]. On the other hand, the adaptations
needed to segment on speed in the 3-dimensional case are trivial. In general, if T EST and
F URTHEST have efficient implementations in the 3-dimensional case, then segmentation is
efficient as well.
In this paper we segment a trajectory by partitioning it into as few pieces as possi-
ble. Interesting related tasks are computing segmentations with overlap and segmenta-
tions that allow for non-homogeneous pieces. We can adapt our segmentation technique
to include non-homogeneous pieces by joining short segments and marking these as ’non-
homogeneous’. We note that a recent paper [41] considers the problem of finding possibly
overlapping pieces of a trajectory that are ’interesting’ according to a given measure.
The application of our framework (which we presented using abstract spatiotemporal
attributes) to domain specific tasks requires the conversion of semantically relevant charac-
teristics of trajectories into attributes related to the ones we considered, but specific for the
purpose. This needs to be done in close collaboration with domain experts and is a topic
for further research.
Acknowledgments
Maike Buchin is supported by the Netherlands Organisation for Scientific Research NWO
(project ACATA) and partially supported by EU Cost action IC0903 (MOVE). Anne Driemel
is supported by the Netherlands Organisation for Scientific Research NWO (project
RIMGA). Marc van Kreveld is partially supported by EU Cost action IC0903 (MOVE).
Vera Sacristán is partially supported by projects MTM2009-07242 and Gen. Cat. DGR
2009SGR1040.
References
[1] A GARWAL , P. K., H AR -P ELED , S., M USTAFA , N. H., AND WANG , Y. Near-linear time
approximation algorithms for curve simplification. Algorithmica 42 (2005), 203–219.
doi:10.1007/s00453-005-1165-y.
[2] A NAGNOSTOPOULOS , A., V LACHOS , M., H ADJIELEFTHERIOU , M., K EOGH , E., AND
Y U , P. Global distance-based segmentation of trajectories. In Proceedings of the 12th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)
(2006), pp. 34–43. doi:10.1145/1150402.1150411.
[3] B ELLMAN , R. On the approximation of curves by line segments using dynamic pro-
gramming. Communications of the ACM 4 (1961), 284. doi:10.1145/366573.366611.
[4] B ENHAMOU , S. How to reliably estimate the tortuosity of an animal’s path: straight-
ness, sinuosity, or fractal dimension? Journal of Theoretical Biology 229 (2004), 209–220.
doi:10.1016/j.jtbi.2004.03.016.
[5] B OVET, P., AND B ENHAMOU , S. Optimal sinuosity in central place foraging move-
ments. Animal Behaviour 42, 1 (1991), 57–62. doi:10.1016/S0003-3472(05)80605-0.
[6] B RAUN , J. V., AND M ÜLLER , H.-G. Statistical methods for DNA sequence segmenta-
tion. Statistical Science 13 (1998), 142–162. doi:10.1214/ss/1028905933.
[7] B UCHIN , K., B UCHIN , M., AND G UDMUNDSSON , J. Detecting single file movement.
In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Ge-
ographic Information Systems (2008), pp. 288–297. doi:10.1145/1463434.1463476.
[8] B UCHIN , K., B UCHIN , M., G UDMUNDSSON , J., L ÖFFLER , M., AND L UO , J. Detecting
commuting patterns by clustering subtrajectories. International Journal of Computational
Geometry and Applications, special issue on 19th International Symposium on Algorithms and
Computation (ISAAC) 21, 3 (2011), 253–282. doi:10.1142/S0218195911003652.
[9] B UCHIN , M., D RIEMEL , A., VAN K REVELD , M., AND S ACRISTAN , V. An algorithmic
framework for segmenting trajectories based on spatio-temporal criteria. In Proceed-
ings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic
Information Systems (2010), pp. 202–211. 10.1145/1869790.1869821.
[10] C HUNDI , P., AND R OSENKRANTZ , D. J. Segmentation of Time Series Data, 2nd ed. Her-
shey: IGI Global, 2009, pp. 1753–1758. doi:10.4018/978-1-60566-010-3.ch267.
www.josis.org
S EGMENTING T RAJECTORIES 61
[11] C LARKSON , K., M EHLHORN , K., AND S EIDEL , R. Four results on randomized incre-
mental constructions. Computational Geometry: Theory and Applications 3 (1993), 185–
212. doi:10.1016/0925-7721(93)90009-U.
[12] D ARK , S. J., AND B RAM , D. The modifiable areal unit problem (maup)
in physical geography. Progress in Physical Geography 31 (2007), 471–479.
doi:10.1177/0309133307083294.
[13] DE B ERG , M., B OSE , P., B REMNER , D., R AMASWAMI , S., AND W ILFONG , G. Com-
puting constrained minimum-width annuli of point sets. In Proceedings of the 5th Inter-
national Workshop on Algorithms and Data Structures (WADS) (1997), vol. 1272 of LNCS,
pp. 392–401. doi:10.1007/3-540-63307-3 77.
[14] DE B ERG , M., C HEONG , O., VAN K REVELD , M., AND O VERMARS , M. Computational
Geometry: Algorithms and Applications, 3rd ed. Springer, Berlin, 2008.
[15] D ODGE , S., W EIBEL , R., AND F OROOTAN , E. Revealing the physics of move-
ment: Comparing the similarity of movement characteristics of different types of
moving objects. Computers, Environment and Urban Systems 33, 6 (2009), 419–434.
doi:10.1016/j.compenvurbsys.2009.07.008.
[16] F U , K., AND M UI , J. A survey on image segmentation. Pattern Recognition 13, 1 (1981),
3–16. doi:10.1016/0031-3203(81)90028-5.
[17] G UIBAS , L., K NUTH , D., AND S HARIR , M. Randomized incremental construc-
tion of Delaunay and Voronoi diagrams. Algorithmica 7, 4 (1992), 381–413.
doi:10.1007/BFb0032048.
[18] G URARIE , E., A NDREWS , R. D., AND L AIDRE , K. L. A novel method for identifying
behavioural changes in animal movement data. Ecology Letters 12, 5 (2009), 395–408.
doi:10.1111/j.1461-0248.2009.01293.x.
[19] H ARGUESS , J., AND A GGARWAL , J. Semantic labeling of track events using time series
segmentation and shape analysis. In Proceedings of the 16th IEEE International Confer-
ence on Image Processing (ICIP) (2009), pp. 4317–4320. doi:10.1109/ICIP.2009.5413671.
[21] H ERSHBERGER , J., AND S URI , S. Off-line maintenance of planar configurations. Algo-
rithms 21 (1996), 453–475. doi:10.1006/jagm.1996.0054.
[22] H IMBERG , J., K ORPIAHO , K., M ANNILA , H., T IKANM ÄKI , J., AND T OIVONEN , H.
Time series segmentation for context recognition in mobile devices. In Proceedings
of the 2001 IEEE International Conference on Data Mining (ICDM) (2001), pp. 203–210.
doi:10.1109/ICDM.2001.989520.
[23] I RISSON , J.-O., L E VAN , A., L ARA , M. D., AND P LANES , S. Strategies and trajectories
of coral reef fish larvae optimizing self-recruitment. Journal of Theoretical Biology 227, 2
(2004), 205–218. doi:10.1016/j.jtbi.2003.10.016.
[24] J ONSEN , I. D., F LEMMING , J. M., AND M YERS , R. A. Robust stateñspace modeling of
animal movement data. Ecology 86 (2005), 2874–2880. doi:10.1890/04-1852.
[25] L ARSON , J. S., B RADLOW, E. T., AND FADER , P. S. An exploratory look at supermar-
ket shopping paths. International Journal of Research in Marketing 22, 4 (2005), 395 – 414.
doi:10.1016/j.ijresmar.2005.09.005.
[26] L EWINER , T., G OMES J R ., J., L OPES , H., AND C RAIZER , M. Curvature and torsion
estimators based on parametric curve fitting. Computers & Graphics 29 (2005), 641–655.
doi:10.1016/j.cag.2005.08.004.
[27] M ANN , R., J EPSON , A., AND E L -M ARAGHI , T. Trajectory segmentation using dy-
namic programming. In Proceedings of the 16th International Conference on Pattern Recog-
nition (ICPR) (2002), pp. 331–334. doi:10.1109/ICPR.2002.1044709.
[28] M ATOU ŠEK , J., S HARIR , M., AND W ELZL , E. A subexponential bound for linear pro-
gramming. Algorithmica 16 (1996), 498–516. doi:10.1007/BF01940877.
[30] N ATHAN , R., G ETZ , W., R EVILLA , E., H OLYOAK , M., K ADMON , R., S ALTZ , D.,
AND S MOUSE , P. A movement ecology paradigm for unifying organismal move-
ment research. Proceedings of the National Academy of Sciences 105 (2008), 19052–19059.
doi:10.1073/pnas.0800375105.
[33] R AJAGOPALAN , V., R AY, A., S AMSI , R., AND M AYER , J. Pattern identification in
dynamical systems via symbolic time series analysis. Pattern Recognition 40, 11 (2007),
2897–2907. doi:10.1016/j.patcog.2007.03.007.
[35] T ERZI , E., AND T SAPARAS , P. Efficient algorithms for sequence segmentation. In
Proceedings of the Sixth SIAM International Conference on Data Mining (2006).
[36] VAN L OON , E., S ACK , J.-R., B UCHIN , K., B UCHIN , M., DE B ERG , M., VAN K REVELD ,
M., G UDMUNDSSON , J., AND M OUNTAIN , D. Results of the break-out group: Gulls
Data. In Dagstuhl Seminar 10491: Representation, Analysis and Visualization of Moving
Objects (2011), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany.
[37] VAN M OORTER , B., V ISSCHER , D. R., J ERDE , C. L., F RAIR , J. L., AND M ERRILL , E. H.
Identifying movement states from location data using cluster analysis. The Journal of
Wildlife Management 74, 3 (2010), 588–594. doi:10.2193/2009-155.
www.josis.org
S EGMENTING T RAJECTORIES 63