Geoscience Reference
In-Depth Information
Algorithm 9.1
Step 1. Compute the planar graph generated by the cells and the
two sets of lexicographical locations
X
1;2
;
X
2;1
.
X
1;2
\
X
2;1
¤;
then set
X
Par
WD
conv.
X
1;2
/
(trivial case
X
.f
1
/
\
Step 2.
If
X
.f
2
/
¤;
). Otherwise set
X
Par
WD
X
1;2
[
X
2;1
(non trivial case
X
.f
1
/
\
X
.f
2
/
D;
)
Step 3.
X
1;2
\
.
Step 4. Scan the list of cells a
dj
acent to
x
until we get situation
S
1
for a cell C
or two consecutive cells, C,
C
, in situations C
2f
S2;S3
g
and
C
2f
S2;S4
g
,
respectively.
Step 5.
Choose
x
2
IP
X
Par
WD
X
Par
[
C
(we have found a bounded
If situation A occurs then
X
Par
[
xy where
y
is a vertex of
C
defined in situations
S2
and
S4
(we have found a bounded face.)
Step 6.
X
Par
WD
cell.) Otherwise
Let
C
be the last scanned cell. Choose
y
2
IP
\
C
and, such that,
y
is
X
2;1
stop. Otherwise, set
x
WD
y
and go to Step 4.
connected to
x
.If
y
2
X
Par
f
1
;f
2
.
Output:
Edelsbrunner (
1987
) proved that the computation of a planar graph induced by
n lines in the plane can be done in O.n
2
/ time. This implies that in the case of
the minisum location problem the computation of the planar graph generated by the
fundamental direction lines is doable in O.M
2
G
max
/ time.
The evaluation of the minisum location function needs O.M log.G
max
// for
one point, therefore we obtain O.M
3
G
max
log .G
max
// time for the computation
of lexicographic solutions. At the end, the complexity for computing the chain is
O.M
3
G
max
log .G
max
//, since we have to consider at most O.M
2
G
max
/ cells and the
determination of
sit
.:;:/can be done in O.M log.G
max
// time. Hence, the overall
complexity is O.M
3
G
max
log .G
max
//. Notice that the polynomial complexity of
this algorithm allows an efficient computation of the solution set.
Example 9.6
Consider a three-criteria median problem with nine existing facilities
A
Df
a
1
;:::;a
9
g
(see Fig.
9.10
). The coordinates a
i
D
.x
i
;y
i
/ of the existing
facilities are given by the set:
f
.
3;0/;.3;0/;.0;
4/;.11;
6/;.17;
6/;.14;
2/;
.11;2/; .17;2/;.14;6/
g
,
w
q
;q
D
1;2;3 are
and
the
weights
given
by
w
1
D
.2;2;1;0;0;0;0;0;0/,
w
2
D
.0;0;0;2;2;1;0;0;0/ and
w
3
D
.0;0;0;0;0;0;2;2;1/.
The optimal solutions of the location problems associated with the median
functions f
1
, f
2
and f
3
with f
q
D
P
iD1
w
i
k
x
a
i
k
1
, q
D
1;2;3, are unique
and given by
X
3
Df
.14;2/
g
, respectively,
all of them with the (optimal) objective value 16. The bicriteria chains (consisting
of cells and edges with respect to the fundamental directions drawn in Fig.
9.10
)are
given by
X
1
Df
.0;0/
g
,
X
2
Df
.14;
6/
g
and
X
Par
f
1
;f
3
D
.0;0/.3;0/
[
conv.
f
.3;0/;.3;2/;.11;2/;.11;0/
g
/
[
.11;2/.14;2/;
X
Par
f
2
;f
3
D
.14;2/.14;
6/;
