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
Search WWH ::




Custom Search