Database Reference
In-Depth Information
t2
t5
t4
t
t3
t2
y
t1
x
t1
Figure 5.3 Space-time prisms and lifeline necklaces.
Definition 5.3. The
space-time prism
with origin
p
=
(
t
p
,x
p
,y
p
), destination
q
=
(
t
q
,x
q
,y
q
), with
t
p
≤
t
q
, and maximal speed
v
max
≥
0 is the set of all points
(
t,x,y
)
∈
R
×
R
2
that satisfy the following constraint formula.
x
p
)
2
y
p
)
2
B
(
t,x,y,t
p
,x
p
,y
p
,t
q
,x
q
,y
q
,v
max
):
=
(
x
−
+
(
y
−
≤
(
t
−
t
p
)
2
v
max
∧
(
x
−
x
q
)
2
+
(
y
−
y
q
)
2
≤
(
t
q
−
t
)
2
v
max
∧
t
p
≤
t
≤
t
q
.
In the formula
B
(
t,x,y,t
p
,x
p
,y
p
,t
q
,x
q
,y
q
,v
max
),
t,x,y
are variables
defining the subset of
R
×
R
2
, while all the other terms are parameters.
5.3.3 Uncertainty in Road Networks
So far we have not made any assumption about where the trajectories under
study develop. These trajectories are usually called
unconstrained.
However,
in general, trajectories develop within a road network in
R
2
. In this case, they
are denoted
constrained
trajectories. This constrained movement has its own
peculiarities. Before studying them, we first need to formalize the notion of a
road network.
Definition 5.4. A
road network
RN
is a graph embedding in
2
a labeled graph
R
2
given by a finite set of vertices
V
={
,
and a set of
edges
E
⊆
V
×
V
that are labeled by a
speed limit
and an associated
time span
.
This graph embedding satisfies the following conditions. Edges are embedded as
straight line segments between vertices, and may intersect in nonvertex points,
to support modeling bridges and tunnels. If an edge is labeled by the speed limit,
then its time span is the time needed to get from one side of an edge to another
when traveling at the speed limit.
(
x
i
,y
i
)
∈
R
|
i
=
1
,...,N
}
