Geoscience Reference
In-Depth Information
subject to d
j
v
j
a
C
b for j
D
1;:::;n
(7.10)
d
j
v
j
a
b for j
D
1;:::;n
(7.11)
d
j
0 for j
D
1;:::;n
(7.12)
a
D
D
1
(7.13)
b;a
i
2
R
for i
D
1;:::;D
1:
(7.14)
For the minmax problem, the objective (
7.9
) has to be replaced by the minmax
objective function f
max
, i.e., by
minimize
jD1;:::;n
w
j
d
j
;
max
which can be rewritten as linear program by using a bottleneck variable
z
and then
replacing the objective by Minimize
z
and adding
w
j
d
j
z
for j
D
1;:::;n as
constraints. It is also possible to use other types of objective functions. For the
minsum problem (see Zemel
1984
) and for the minmax problem (see Megiddo
1984
), the above LP formulation can be solved in O(n) time.
Now consider a block norm
B
with unit ball B
D
conv
f
e
1
;:::;e
G
g
, i.e., e
g
;g
D
1;:::;G are the
fundamental directions
of the block norm. The idea is to solve the
problem for each of the fundamental directions separately. To this end, we extend
the vertical distance d
ver
to a distance d
t
, t
2
D
as follows.
d
t
.
u
;v/
WD
j
Ǜ
j
if
u
v
D
Ǜt for some Ǜ
2
R
R
1
otherwise:
We then know the following result.
Lemma 7.4 (Schöbel
1999a
)
Let
H
be a hyperplane and let
d
be derived from a
block norm
B
with fundamental directions
e
1
;:::;e
G
. Then for any point
v
2
D
R
there exists
N
g
2f
1;:::;G
g
such that
d.H;v/
D
d
e
g
.H;v/
D
min
gD1;:::;G
d
e
g
.H;v/;
i.e., the fundamental direction
e
g
is independent of the point
v
.
This result allows to solve the problem with block norm distance in O(Gn) time
in the planar case by iteratively solving the minmax hyperplane location problem
with respect to distance d
e
g
, g
D
1;:::;G, and taking the best solution. Note
that the G problems may be solved by transformation to the vertical distance as
follows: Choose a linear (invertible) transformationT with T.e
g
/
D
.0;0;:::;0;1/.
Transform all points v
0
j
D
T.v
j
/;j
D
1;:::;n. We obtain that
d
ver
.T.H/;T.v//
D
d
e
g
.H;v/
