Geoscience Reference
In-Depth Information
7.4.3.2
Location of Minsum Circles and Hyperspheres with Block Norms
If d is derived from a block norm, a finite dominating set can be constructed for
the center point of the minsum circle. To this end, graph all fundamental directions
f
e
1
;:::;e
G
g
2
of the block norm through any of the existing points v
2
V and
add the bisectors for all pairs of existing points in V . The intersection points of these
lines are a finite dominating set which can be tested within O(n
3
) time, see Körner
(
2011
) and Brimberg et al. (
2011a
).
Using that the block norm of a point y is given as
R
X
G
X
G
k
y
kD
min
f
Ǜ
g
W
y
D
Ǜ
g
e
g
;Ǜ
g
0 for g
D
1;:::;G
g
gD1
gD1
the problem can in the case of block norms alternatively be formulated as the
following linear program with nG
C
2n
C
D
C
1 variables, see Brimberg et al.
(
2011a
) for the planar case and Körner et al. (
2012
) for the case of hyperspheres.
w
j
z
j
C
z
j
X
n
minimize
jD1
X
G
Ǜ
g;j
D
r
C
z
j
z
j
for j
D
1;:::;n
subject to
gD1
X
G
Ǜ
g;j
e
g
D
x
v
j
for j
D
1;:::;n
gD1
z
j
;
z
j
0 for j
D
1;:::;n
Ǜ
g;j
0 for g
D
1;:::;G;j
D
1;:::;n
r
0
D
:
x
2
R
7.4.4
The Minmax Hypersphere Location Problem
We now turn our attention to the location of a minmax hypersphere, i.e., we look for
a hypersphere which minimizes the maximum weighted distance from its surface to
the set V of existing points. Given a distance d derived from a norm, the goal hence
is to find a hypersphere S
D
S
x;r
which minimizes
X
n
f
max
.S
x;r
/
D
max
jD1
w
j
d.S
x;r
;v
j
/
D
w
j
j
d.x;v
j
/
r
j
:
(7.19)
jD1