Geoscience Reference
In-Depth Information
X
Par
,wehave
Second, since x
2
\
2
\
2
L
.f
q
;f
q
.
z
//
D
L
D
.f
q
;f
q
.
z
//
8
z
2
ab
:
qD1
qD1
X
Par
.
Case 3: x
2
Ext.C/. We can choose y
2
int.C/ and two cases can occur
X
Par
Hence, we have that C
6
and
ab
X
Par
, we can continue as in Case 1.
Case 3.1:
If y
2
X
Par
, we choose
z
1
;
z
2
2
Ext.C/ such that
xz
1
;
xz
2
are
Case 3.2:
If y
…
faces of C,
X
Par
, we can continue as in Case 2.
- f
z
1
and
z
2
are not in
- f
z
1
or
z
2
are in
X
Par
, then using the linearity in the same way as
before we obtain that .C
nf
x
g
/
\
X
Par
D;
.
Hence, we conclude that the set of Pareto solutions consists of complete cells,
complete faces, and vertices of these cells. Since we know that the set
X
Par
is
connected, the proof is completed.
In the following we develop an algorithm to solve the bicriteria planar minisum
location problem. The idea of this algorithm is to start in a vertex x of the cell
structure which belongs to
X
1;2
WD
arg min
x2
X
.f
1
/
f
2
.x/ (set of
optimal lexicographical locations, see Nickel
1995
). Then, using the connectivity of
X
Par
, the algorithm proceeds by moving from vertex x to another Pareto-optimal
vertex y of the cell structure which is connected with the previous one by an
elementary convex set. This procedure is repeated until the end of the chain reaches
X
2;1
WD
arg min
x2
X
.f
2
/
f
1
.x/.
Let C be a cell and y, x and
z
three vertices of C enumerated counterclockwise
(see Fig.
9.8
). By the linearity of the level sets in each cell we can distinguish the
following disjoint situations, if x
2
X
Par
,sayx
2
X
Par
:
X
Pa
r
(S1)
C
, i.e., C is contained in the chain.
X
Par
X
Par
.
(S2)
xy
and
xz
are candidates for
and int.C/
6
X
Par
X
Par
.
(S3)
xy
is candidate for
and
xz
is not contained in
X
Par
X
Par
.
(S4)
xz
is can
di
date
fo
r
and
xy
is not contained in
X
Par
.
We denote by
sit
.C;x/ the situations (S1-S4 or S5) in which the cell C is
classified according to the extreme point x of C. The following lemma, whose proof
is based on an exhaustive case analysis of the different relative positions of x within
C, can be found in Weissler (
1999
). It states when a given segment belongs to the
Pareto-set in terms of the
sit
.
;
/ function.
(S5)
Neither
xy
nor
xz
are contained in
Lemma 9.1
Let
C
1
;:::;C
P
x
be the cells containing the intersection point
x
,
considered in counterclockwise order, and
y
1
;:::;y
P
x
the intersection points
adjacent to
x
, considered in counterclockwise order (see Fig.
9.9
). If
x
2
X
Par
