Geoscience Reference
In-Depth Information
Fig. 10.2
A three-node
network with
EQ
D
f
EQ
12
;
EQ
13
;
EQ
23
;v
1
;v
2
;v
3
g
and the geometrical
subdivision
v
1
1
2
3
1
3
2
2
1
3
EQ
12
EQ
13
3
1
2
EQ
23
v
2
v
3
2
3
1
3
2
1
Fig. 10.3
The network used
in Example
10.3
2
v
1
v
3
2
3
1
v
2
v
6
3
3
1
3
2
v
4
v
5
2
For algorithmic purposes one should note that the set
EQ
can be computed by
intersection of all distance functions, see (
10.26
) on all edges. Since a distance
function has maximally one breakpoint on every edge we can use a line sweep
technique to determine
EQ
on one edge in O..n
C
k/log n/,wherek
n
2
is the
number of intersection points. Therefore we can compute
EQ
for the whole network
in O.m.n
C
k/log n/ time. Of course, this is a worst-case bound and the set of
candidates can be further reduced by some domination arguments: Take for two
candidates x, y the corresponding weighted (and sorted) distance vectors d
.x/,
d
.y/.Ifd
.x/ is in every component strictly smaller than d
.y/ then there is
no positive with which f
.d.y//
f
.d.x//. This domination argument can
be integrated in any line sweep technique reducing, in most cases, the number of
candidates.
Example 10.3
Consider the network given in Fig.
10.3
with
w
1
D
w
2
D
w
5
D
1
and
w
3
D
w
4
D
w
6
D
2.Table
10.3
lists the set
EQ
, where the labels of the rows
EQ
ij
indicate that i, j are the vertices under consideration and the columns indicate
the edge e
Df
r;s
g
. The entry in the table gives for a point x
D
.e;t/ the value of t
(if t is not unique an interval of values is shown).
Now we only have to evaluate the objective function with a given set of -values
for
EQ
and determine the optima. Table
10.4
gives the solutions for some specific
