Geoscience Reference
In-Depth Information
is minimal (with a
D
D
1). In order to get rid of the absolute values, we define
H
a;b
WDf
j
2f
1;:::;n
gW
v
t
j
a
C
b>0
g
H
a;b
WDf
j
2f
1;:::;n
gW
v
t
j
a
C
b<0
g
H
a;b
WDf
j
2f
1;:::;n
gW
v
t
j
a
C
b
D
0
g
:
We furthermore set
W
a;b
WD
X
j2H
a;b
w
j
; W
a;b
WD
X
j2H
a;b
w
j
; W
a;b
WD
X
j2H
a;b
w
j
and let W
WD
P
jD1
w
j
be the sum of all weights. Since f
1
.a;b/ is piecewise linear
in b we receive:
Theorem 7.1 (Halving Property for Minsum Hyperplanes)
(Schöbel
1999a
;
Martini and Schöbel
1998
)Let
H
a;b
be a minsum hyperplane w.r.t the vertical
distance
d
ver
.Then
W
a;b
W
2
and
W
a;b
W
2
(7.5)
Note that the halving property (
7.5
) is equivalent to
W
a;b
W
a;b
C
W
a;b
and W
a;b
W
a;b
C
W
a;b
:
(7.6)
Looking again at (
7.4
), note that f
1
is not only piecewise linear in b but is also
convex and piecewise linear in the D variables a
1
;:::;a
D1
;b. The latter yields the
following
incidence property
.
Theorem 7.2 (FDS for Minsum Hyperplanes with Vertical Distance)
Let
d
ver
be the vertical distance and let
n
D
. Then there exists a minsum hyperplane w.r.t
d
ver
that passes through
D
affinely independent points.
Sketch of Proof
We can rewrite the objective function f
1
.H
a;b
/ to
f
1
.H
a;b
/
D
X
j2H
a;b
w
j
.v
t
j
a
C
b/
C
X
jW2H
a;b
w
j
.
v
t
j
a
b/
(7.7)
which is easily seen to be linear as long as the signs of v
t
j
a
C
b do not change, i.e.,
on any polyhedral
cell
given by disjoint sets H
;H
specifying which existing
points should be below (or on) and above (or on) the hyperplane:
R.H
;H
/
WD
˚
.a
1
;:::;a
D1
;b/
W
v
t
j
a
C
b
0 for all j
2
H
v
t
j
a
C
b
0 for all j
2
H
o
:
