Geoscience Reference
In-Depth Information
Note that these polyhedra can be constructed in dual space by using the arrangement
of hyperplanes T
H
.v
j
/;j
D
1;:::;n, i.e., the right hand side of Fig.
7.2
shows
exactly the polyhedra in dual space on which the objective function is linear. The
fundamental theorem of linear programming then yields an optimal solution at a
vertex of some of the cells R.H
;H
/, i.e., a hyperplane satisfying v
t
j
a
C
b
D
0
for at least D indices from
f
1;:::;n
g
.
t
Note that many papers mention this result. For D
D
2,itwasshownin
We s o l ow s ky (
1972
), Morris and Norback (
1983
), Megiddo and Tamir (
1983
)and
generalized to higher dimensions, e.g., in Schöbel (
1999a
).
In our example of Fig.
7.2
the depicted line is an optimal solution.
7.3.3.2
Minsum Hyperplane Location with Norm-Based Distance
We now turn our attention to the location of hyperplanes with respect to a norm
kk
.
In this case, we can use Lemma
7.2
and obtain the following objective function
X
n
w
j
j
v
t
a
C
b
j
k
a
k
ı
f
1
.H
a;b
/
D
(7.8)
jD1
where
kk
ı
denotes the dual norm of
kk
. Still, the objective function is piecewise
linear in b, hence the halving property holds again:
Theorem 7.3 (Halving Property for Minsum Hyperplanes)
(Schöbel
1999a
;
Martini and Schöbel
1998
)Let
d
be a norm and
H
a;b
be a minsum hyperplane
w.r.t
d
.Then
W
a;b
W
2
and
W
a;b
W
2
We also receive the incidence property of Theorem
7.2
.
Theorem 7.4 (FDS for Minsum Hyperplanes)
(Schöbel
1999a
; Martini and
Schöbel
1998
,
1999
)Let
d
be derived from a norm and let
n
D
. Then there exists
a minsum hyperplane w.r.t
d
that passes through
D
affinely independent points. If
and only if the norm is smooth, we have that
all
minsum hyperplanes pass through
D
affinely independent points.
Sketch of Proof
Different proofs for this property exist. Here, we use the cell
structure of the proof of Theorem
7.2
for the vertical distance. The idea is to use
piecewise quasiconcavity instead of piecewise linearity on these cells. Neglecting
